4 Problem B : 타일 채우기

정사각형 모양의 바닥을 타일로 채우려고 함

타일의 모양 4가지가 존재함

홀의 위치를 입력 받고, 홀을 제외한 나머지 부분은 빈 공간 없이 타일을 채우는 프로그램을 작성하시오

- 분할 정복

- 홀의 위치

- 재귀로 풀이 가능

- 행,렬 명확히 구분

 

#include <stdio.h>

#define MAX 520
int tile[MAX][MAX];
int dy[4] = { 0, 0, 1, 1 }, dx[4] = { 0,1,0,1 };

void fill(int n, int sy, int sx, int hy, int hx)
{
	if (n < 2) return; // n==1이면 return
	int m = n / 2, my = sy + m, mx = sx + m, y, x; // 중간위치가 어디인지 확인
	int hp = hy/my * 2 + hx/mx; // 사분면의 위치를 정하는 것
	
	for (int i = 0; i < 4; i++) {
		if (i == hp) fill(m, sy + m * dy[i], sx + m * dx[i], hy, hx); // 내쪽에 홀이 있다면
		else { // 홀이 없다면 채워야 함
			y = my - 1 + dy[i], x = mx - 1 + dx[i];
			tile[y][x] = hp + 1; // 홀 주변 빈칸에 알맞은 값을 넣음
			fill(m, sy + m * dy[i], sx + m * dx[i], y, x);
		}
	}
}

int main()
{
	int n, hy, hx;
	scanf("%d %d %d", &n, &hy, &hx);
	fill(n, 0, 0, hy, hx); // 시작 위치와 구멍의 위치
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) printf("%d ", tile[i][j]);
		printf("\n");
	}
	return 0;
}

8 2 3

4 4 3 3 4 4 3 3 4 4 4 3 4 3 3 3 2 4 2 0 3 3 3 1 2 2 2 2 1 3 1 1 4 4 2 1 1 1 3 3 4 2 2 2 1 1 1 3 2 2 2 1 2 1 1 1 2 2 1 1 2 2 1 1