4 Problem B : 타일 채우기

Problem B : 타일 채우기

 

제한시간: 1000 ms    메모리제한: 64 MB
Special Judge

 

 

정사각형 모양의 화장실 바닥을 타일로 채우려고 한다.
화장실의 바닥에는 배수구가 있는데 이곳에는 타일을 놓을 수 없다.
타일의 모양은 다음과 같은 4가지 종류가 있다.

 

 

 

화장실 바닥의 한 변의 길이와 배수구의 위치를 입력으로 받아서 

배수구를 제외한 나머지 부분에 빈 공간 없이 타일을 채우는 프로그램을 작성하시오.

 

첫 번째 줄에는 화장실 바닥의 한 변의 길이 N을 입력받는다. ( 2≤N≤512, N은 2의 거듭제곱 2, 4, 8, 16...) 다음 줄에는 구멍의 위치 X , Y를 입력받는다. X는 위쪽으로부터의 거리, Y는 왼쪽으로부터의 거리를 의미한다. (0≤X,Y<N)

 

 

화장실 바닥의 각 위치에 배치한 타일의 번호를 모두 출력한다. 구멍의 위치에는 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

 

#include <stdio.h>

#define MAX 10 // 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; // 한칸 씩만 남았으면
	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++) { // 4칸이므로
		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()
{
	freopen("input.txt", "r", stdin);
	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;
}