编程实现棋盘覆盖问题的c 程序
时间: 2023-09-03 10:11:04 浏览: 96
棋盘覆盖问题是指,在一个 $2^k \times 2^k$ 的棋盘上,去掉其中一个格子后,用 L 形骨牌覆盖整个棋盘。下面是 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define BOARD_SIZE 1024 // 棋盘大小
#define BLOCK_SIZE 2 // 骨牌大小
int board[BOARD_SIZE][BOARD_SIZE]; // 棋盘
// 递归函数,用 L 形骨牌覆盖棋盘
void cover(int tr, int tc, int dr, int dc, int size, int id)
{
if (size == 1) {
return;
}
int tsize = size / 2;
int nid = id + 1;
// 情况 1
if (dr < tr + tsize && dc < tc + tsize) {
cover(tr, tc, dr, dc, tsize, id);
} else {
board[tr + tsize - 1][tc + tsize - 1] = id;
cover(tr, tc, tr + tsize - 1, tc + tsize - 1, tsize, id);
}
// 情况 2
if (dr < tr + tsize && dc >= tc + tsize) {
cover(tr, tc + tsize, dr, dc, tsize, nid);
} else {
board[tr + tsize - 1][tc + tsize] = id;
cover(tr, tc + tsize, tr + tsize - 1, tc + tsize, tsize, nid);
}
// 情况 3
if (dr >= tr + tsize && dc < tc + tsize) {
cover(tr + tsize, tc, dr, dc, tsize, nid);
} else {
board[tr + tsize][tc + tsize - 1] = id;
cover(tr + tsize, tc, tr + tsize, tc + tsize - 1, tsize, nid);
}
// 情况 4
if (dr >= tr + tsize && dc >= tc + tsize) {
cover(tr + tsize, tc + tsize, dr, dc, tsize, nid);
} else {
board[tr + tsize][tc + tsize] = id;
cover(tr + tsize, tc + tsize, tr + tsize, tc + tsize, tsize, nid);
}
}
// 初始化棋盘
void init_board()
{
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
board[i][j] = -1;
}
}
}
// 打印棋盘
void print_board()
{
for (int i = 0; i < BOARD_SIZE; i++) {
for (int j = 0; j < BOARD_SIZE; j++) {
if (board[i][j] == -1) {
printf(" ");
} else {
printf("%d", board[i][j]);
}
}
printf("\n");
}
}
int main()
{
int tr, tc, dr, dc; // 棋盘上的空白格子坐标
printf("请输入棋盘上的空白格子坐标(格式为:行 列):");
scanf("%d %d", &tr, &tc);
init_board();
int id = 1;
board[tr][tc] = 0;
cover(0, 0, tr, tc, BOARD_SIZE, id);
print_board();
return 0;
}
```
在程序中,我们使用一个二维数组 `board` 表示棋盘,初始化时所有格子的值为 -1。在递归函数 `cover` 中,我们将棋盘分成四个部分,分别处理每个部分。
递归终止条件是棋盘大小为 1,此时直接返回。
在递归过程中,我们需要根据棋盘空白格子的位置,将棋盘分成四个部分,分别处理。如果空白格子在某个部分内,则继续递归处理该部分;否则,将该部分的右下角格子用当前的骨牌覆盖,并递归处理其他三个部分。
最终,我们调用 `print_board` 函数打印出覆盖后的棋盘。
阅读全文