在一个 2ᵏ × 2ᵏ 个方格组成的棋盘中,若恰有一个方格与其他方格不同(图中标记为 -1 的方格),则称该方格为特殊方格。现在用 L 型(占3个小方格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠,于是用到的纸片数恰好是 (4ᵏ - 1) / 3 。写一个程序,求覆盖方案。
如在下图中,给出的一个覆盖方案中,k = 2 ,那么就是 4 × 4 个方格,那么纸片数恰好是 5 个。
![](/static/upload/1614323648561184.png)
【输入描述】
输入第一行为方阵的规模,也就是数组的行列值。输入第二行两个整数,表示特殊方格的行列下标。
【输出描述】
输出覆盖后的棋盘数组。
【输入样例】
//样例1:
8
4 4
【输出样例】
//样例1:
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 1 1 18 19 19
13 12 14 14 18 18 17 19
15 12 12 16 20 17 17 21
15 15 16 16 20 20 21 21
【参考程序】
//爱码岛编程
#include <bits/stdc++.h>
using namespace std;
// k=6, 64 x 64二维数组(下标从1开始),tile为纸片编号
int board[65][65], tile = 1;
/*
* tr, tc 棋盘的起始行列号, [1, 1]
* size 2ᵏ :2、4、8、16、32、64
* dr, dc 为特殊方格的行列号,比如 [size/2, size/2]
*/
void chessBoard(int tr, int tc, int dr, int dc, int size) {
int t, s;
if (size == 1)
return;
t = tile++;
s = size / 2;
// 左上角
if (dr < tr + s && dc < tc + s) {
chessBoard(tr, tc, dr, dc, s);
} else {
board[tr + s - 1][tc + s - 1] = t;
chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
// 右上角
if (dr < tr + s && dc >= tc + s) {
chessBoard(tr, tc + s, dr, dc, s);
} else {
board[tr + s - 1][tc + s] = t;
chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}
// 左下角
if (dr >= tr + s && dc < tc + s) {
chessBoard(tr + s, tc, dr, dc, s);
} else {
board[tr + s][tc + s - 1] = t;
chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
// 右下角
if (dr >= tr + s && dc >= tc + s) {
chessBoard(tr + s, tc + s, dr, dc, s);
} else {
board[tr + s][tc + s] = t;
chessBoard(tr + s, tc + s, tr + s, tc + s, s);
}
}
int main() {
int size;
int dr, dc;
cin >> size;
cin >> dr >> dc;
board[dr][dc] = -1;
chessBoard(1, 1, dr, dc, size);
//打印
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
cout << setw(5) << board[i][j];
}
cout << endl;
}
return 0;
}