Boj 14601) 샤워실 바닥 깔기

문제

백준 14601

설명

k == 3 일때만 제시해줬으면 매우 쉬웠을 문제.

해가 없을경우 -1 을 주라고 하지만 낚시이다. 2 의 제곱 크기의 정사각형은 2x2 기역자 블럭으로 1칸 빼고 다 처리 가능하다.

정사각형을 4분등해서 구멍이 있는 곳은 꽉 채우고, 나머지 3분등은 가운데로 한칸씩 구멍을 내서 추가로 기역자를 만든다. 그럼 언제나 한칸 빼고 꽉 채울 수 있게 된다.

k==3 일 때 예시

 3
 1 2

 3  3  4  4  8  8  9 9
 3  2  2  4  8  7  7 9
 5  2  6  6 10 10  7 11
 5  5  6  1  1 10 11 11
13 13 14 14  1 18 19 19
13 12 12 14 18 18 17 19
-1 15 12 16 20 17 17 21
15 15 16 16 20 20 21 21

시간 복잡도

O(전체판크기)

코드

int bwidth = 1;
int board[129*129];
int nTile = 1;

enum DIR { LT = 0, RT = 1, LB = 2, RB = 3};

void Fill2x2(int x, int y, DIR dir)
{
    if(dir != LT) board[bwidth * y + x] = nTile;  
    if(dir != RT) board[bwidth * y + x + 1] = nTile;
    if(dir != LB) board[bwidth * (y + 1) + x] = nTile;
    if(dir != RB) board[bwidth * (y + 1) + x + 1] = nTile;
    nTile++;
}
void Fill2x2(int x, int y, int hole_x, int hole_y)
{
    Fill2x2(x, y, (DIR)((hole_y-y)*2 + hole_x-x));
}

void Devide(int width, int left, int top, int hole_x, int hole_y)
{

    int half = width / 2;
    DIR dir = DIR((hole_y-top) / (half) * 2 + (hole_x-left)/(half));
    if (width == 2)
    {
        Fill2x2(left, top, hole_x, hole_y);
        return;
    }
    
    Fill2x2(left + half - 1, top + half - 1, dir);
    if (dir != LT) Devide(half, left, top,                left + half - 1, top + half - 1); else { Devide(half, left, top,           hole_x, hole_y); }
    if (dir != RT) Devide(half, left+half, top,           left + half - 0, top + half - 1); else { Devide(half, left+half, top,      hole_x, hole_y); }
    if (dir != LB) Devide(half, left, top+half,           left + half - 1, top + half - 0); else { Devide(half, left, top+half,      hole_x, hole_y); }
    if (dir != RB) Devide(half, left+half, top+half,      left + half - 0, top + half - 0); else { Devide(half, left+half, top+half, hole_x, hole_y); }
}

int main()
{
    int k; int hole_x, hole_y;
    cin >> k >> hole_x >> hole_y;
    bwidth = 2 << k-1;
    hole_x--; hole_y = bwidth - hole_y;
    
    board[bwidth * hole_y + hole_x] = -1;
    Devide(bwidth, 0, 0, hole_x, hole_y);
    
    for (int i = 0; i < bwidth; i++)
    {
        for (int j = 0; j < bwidth; j++)
            printf("%d ", board[i * bwidth + j]);
        printf("\n");
    }
}