[정올 2543] 타일 채우기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1804&sca=99&sfl=wr_hit&stx=2543 

JUNGOL

#include <stdio.h>

/*  분할 정복 문제
    1. 처음에 N * N 행렬이 있고, 채울 수 없는 H이 하나 있다.
    2. 행렬을 4등분하여 H가 없는 사분면 중간에 블럭을 추가한다.
    3. 2번이 끝나면, 각 사분면에 채울 수 없는 1개짜리 블럭이 각각 1개씩 있게 된다. (원래 H있는 사분면 1개 + 블럭 추가한게 1개씩 들어간 사분면 3개)
       즉, 원래 문제와 똑같은데 크기만 4분의 1로 작아진 4개짜리 문제가 생기는 것이다.
    4. 3번에서 생긴 4개의 4분면을 가지고 2번~3번을 반복한다.
       이렇게 반복하면 2 * 2 행렬이 나올 것이고, 4개중 1개가 H인 문제가 된다.
       이 때 H의 위치에 따라 넣어줄 블럭이 달라진다.
       H 1 | 2 H | 3 3 | 4 4
       1 1 | 2 2 | H 3 | 4 H
       >> 이 상황에서 한번 더 쪼개서 1 * 1이 되었을 때 위와 같이 넣어줘야 한다. */

//#define DBG
struct P {
    int r, c; //x가 행(위, ), y가 열(왼
    P() : r(0), c(0) {}
    P(int a, int b) : r(a), c(b) {}
};

P H;
int N, T[513][513]; //x는 위에서부터의 거리, y는 왼쪽으로부터의 거리 (0부터 시작)

void display() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) printf("%d ", T[i][j]);
        printf("\n");
    }
}

void fill2by2(const int r, const int c) { //해당포인트 포함한 2*2를 채움(1개만 구멍임이 보장)
    if (T[r][c]) T[r + 1][c] = T[r][c + 1] = T[r + 1][c + 1] = 1; //1이 구멍
    else if (T[r][c + 1]) T[r][c] = T[r + 1][c] = T[r + 1][c + 1] = 2; //2가 구멍
    else if (T[r + 1][c]) T[r][c] = T[r][c + 1] = T[r + 1][c + 1] = 3; //3이 구멍
    else T[r][c] = T[r][c + 1] = T[r + 1][c] = 4; //4가 구멍
}

void divNconq(P s, P e, P h) { //시작지점, 종료지점, 홀, 완성여부
    if (e.r - s.r == 1) { //2*2이고 h 포함한 경우 >> 채우고 리턴
        fill2by2(s.r, s.c);
        return;
    }
    P m((s.r + e.r) / 2, (s.c + e.c) / 2), s2(s.r, m.c + 1), e2(m.r, e.c), s3(m.r + 1, s.c), e3(e.r, m.c);
    P h2(m.r, m.c + 1), h3(m.r + 1, m.c), h4(m.r + 1, m.c + 1);
    //처음엔 4구역 전부 빈 상태임, 구멍이 있는 구역을 찾은 후에
    if (h.r <= m.r) { //1 or 2구역
        if (h.c <= m.c) { //1구역
            divNconq(s, m, h); //1. 해당 구역을 재귀로 다 채움
            fill2by2(m.r, m.c); //2. 중앙지역을 알맞게채움
            //3. 나머지 3구역을 재귀로 채움
            divNconq(s2, e2, h2); //2
        }
        else { //2구역
            divNconq(s2, e2, h); //2
            fill2by2(m.r, m.c);
            divNconq(s, m, m); //1
        }
        divNconq(s3, e3, h3); //3
        divNconq(h4, e, h4); //4
    }
    else { //3 or 4구역
        if (h.c <= m.c) { //3구역
            divNconq(s3, e3, h); //3
            fill2by2(m.r, m.c);
            divNconq(h4, e, h4); //4
        }
        else { //4구역
            divNconq(h4, e, h); //4
            fill2by2(m.r, m.c);
            divNconq(s3, e3, h3); //3
        }
        divNconq(s, m, m); //1
        divNconq(s2, e2, h2); //2
    }
    return;
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	scanf("%d %d", &H.r, &H.c);
	H.r++, H.c++;
	T[H.r][H.c] = 8;
	P s(1, 1), e(N, N);
	divNconq(s, e, H);
	T[H.r][H.c] = 0;
	display();
	return 0;
}