트로미노 타일링이라고 하는 아주 유명한 문제입니다. 여기서는 불가능하면 -1을 출력하라고 했는데, 사실 항상 가능합니다. 증명은 수학적 귀납법으로 합니다.
$2^n\times 2^n$ 크기의 체스판에서 어느 한 칸이 빠져도 항상 L-트로미노로 덮을
수 있다.
$n=1$인 경우는 너무나도 자명합니다. $n=k$일 때 성립한다고 가정하면 $n=k+1$일
때에는 다음과 같이 체스판을 쪼개 가운데 L-트로미노 하나를 덮고 나머지 네 곳은
$n=k$일 때 덮는 방식으로 덮으면 $n=k+1$일 때에도 항상 덮을 수 있습니다.
재귀함수를 써서 위 증명을 그대로 구현하면 됩니다.
#include<cstdio>
using namespace std;
int floor[128][128];
int pow2 (int n) {
int ans = 1;
for (int i = 0; i < n; i++) ans *= 2;
return ans;
}
void tiling(int r, int c, int k, int rd, int cd, int nstart) {
if (k == 1) {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
if (!(i == rd && j == cd))
floor[r+i][c+j] = nstart;
return;
}
int sh = pow2(k-1);
int didx = 2 * (rd / sh) + cd / sh;
int ntroq = (sh * sh - 1) / 3;
tiling(r + sh * (rd / sh), c + sh * (cd / sh), k-1, rd % sh, cd % sh, nstart);
for (int i = 1; i < 4; i++) {
int idx_nxt = (didx + i) % 4;
int nrd = idx_nxt / 2 == 0? sh-1 : 0;
int ncd = idx_nxt % 2 == 0? sh-1 : 0;
tiling(r + sh * (idx_nxt / 2), c + sh * (idx_nxt % 2), k-1, nrd, ncd, nstart + i*ntroq);
}
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
if (2*i + j != didx)
floor[r+sh-1+i][c+sh-1+j] = nstart + 4 * ntroq;
}
int main(void) {
int k, a, b;
scanf("%d %d %d", &k, &a, &b);
tiling(0, 0, k, a-1, b-1, 1);
floor[a-1][b-1] = -1;
int s = pow2(k);
for (int i = s-1; i >= 0; i--) {
for (int j = 0; j < s; j++)
printf("%d ", floor[j][i]);
printf("\n");
}
return 0;
}