棋盘覆盖

题目：

​ 在一个 2 k ∗ 2 k 2^k*2^k 2k∗2k 个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为特殊棋盘。如下图：

image-20221021232516601

显然特殊方格在棋盘上的位置有 4 k 4^k 4k 种可能。 用四种不同的L型骨牌，如下图：

image-20221021232618135

覆盖一个给定的特殊棋盘上除了特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，在任意一个棋盘中用到的L型骨牌个数为 ( 4 k − 1 ) / 3 (4^k-1)/3 (4k−1)/3 。

输入格式：

三个数分别为k（棋盘尺寸），x，y（特殊点横纵坐标）

输出格式：

共 $ 2^k $ 行，分别表示覆盖该格的L型的编号（特殊格用0表示）。输出字符最小宽度为4，左对齐输出。

例如：

测试输入：
3 3 2
预期输出：
3    3    4    4    8    8    9    9
3    2    2    4    8    7    7    9
5    0    2    6    10   10   7    11
5    5    6    6    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

提示：
特殊骨牌的牌号为0
正常骨牌号从1开始
覆盖棋盘请严格遵循先覆盖左上角,右上角，左下角，右下脚

分析：

​ 可以采用分治思想，将棋盘的行列平均分开，并在交界处补一块L型骨牌，骨牌类型满足，补齐后，使得在跟一个子分块上都有一个覆盖点，如下图：

image-20221022001040592

这样就分化出四个独立子问题，以此类推，直至子问题规模化简为1x1的棋盘。

递归方程为：
T ( k ) = { O ( 1 ) k = 0 4 T ( k − 1 ) + O ( 1 ) k > 0 T(k)= \begin{cases} O(1) && k=0 \\ 4T(k-1)+O(1) && k>0 \end{cases} T(k)={O(1)4T(k−1)+O(1)​​k=0k>0​
可得时间复杂度 $ T(k)=O(4^k) $

实现一：算法书中的方法

参数说明：

tr: 棋盘左上角行坐标
tc: 棋盘右上角列坐标
dr: 特殊格行坐标
dc: 特殊格列坐标
size: 规模大小
  1. 规模减半划分子问题
int halfSize = size / 2;
  1. 覆盖左上部分
    ps：横坐标 tr+halfSize 和纵坐标 tc+halfSize 标识右下的子块的左上方格的坐标，如图：
image-20221022233506994

​ 所以，判断特殊方格是否在左上的表达式为 dr < tr+halfSize && dc < tc+halfSize 。如果在的话，那么特殊方格的坐标保持原来的 dr ，dc ，取左上部分左上角方格坐标，这里是 tr ，tc ，进行递归填充。如果不在的话在右下角填充骨牌 board[tr+halfSize-1][tc+halfSize-1]=tile; 取同样的左上角方格坐标 tr ，tc ，进行递归填充，此时的特殊格横纵坐标变为tr+halfSize-1 和 tc+halfSize-1。其他三种情况类似就展开细说。

// 覆盖左上角子棋盘
if(dr < tr+halfSize && dc < tc+halfSize){
    // 特殊格在左上角
    chessBoard(tr, tc, dr, dc, halfSize);
} else {
    // 特殊格不在左上角，先补齐特殊块，再递归
    board[tr+halfSize-1][tc+halfSize-1]=tile;
    chessBoard(tr, tc, tr+halfSize-1, tc+halfSize-1, halfSize);
}
  1. 覆盖右上部分
// 覆盖右上角子棋盘
if(dr < tr+halfSize && dc >= tc+halfSize){
    // 特殊格在右上角
    chessBoard(tr, tc+halfSize, dr, dc, halfSize);
} else {
    board[tr+halfSize-1][tc+halfSize]=tile;
    chessBoard(tr, tc+halfSize, tr+halfSize-1, tc+halfSize, halfSize);
}
  1. 覆盖左下部分
// 覆盖左下角子棋盘
if(dr >= tr+halfSize && dc < tc+halfSize){
    // 特殊格在左下角
    chessBoard(tr+halfSize, tc, dr, dc, halfSize);
} else {
    board[tr+halfSize][tc+halfSize-1]=tile;
    chessBoard(tr+halfSize, tc, tr+halfSize, tc+halfSize-1, halfSize);
}
  1. 覆盖右下部分
// 覆盖右下角子棋盘
if(dr >= tr+halfSize && dc >= tc+halfSize){
    // 特殊格在右下角
    chessBoard(tr+halfSize, tc+halfSize, dr, dc, halfSize);
} else {
    board[tr+halfSize][tc+halfSize]=tile;
    chessBoard(tr+halfSize, tc+halfSize, tr+halfSize, tc+halfSize, halfSize);
}

代码：

#include<stdio.h>

int domino = 0;  // 当前骨牌标识
int board[1024][1024];  // 棋盘

/**
* tr: 棋盘左上角行坐标
* tc: 棋盘右上角列坐标
* dr: 特殊格行坐标
* dc: 特殊格列坐标
* size: 规模大小
*/
void chessBoard(int tr, int tc, int dr, int dc, int size){
	// 边界条件，规模为1时
	if(size == 1){
		return;
	}
	int halfSize = size / 2;
	int tile = ++domino;
	// 覆盖左上角子棋盘
	if(dr < tr+halfSize && dc < tc+halfSize){
		// 特殊格在左上角
		chessBoard(tr, tc, dr, dc, halfSize);
	} else {
		board[tr+halfSize-1][tc+halfSize-1]=tile;
		chessBoard(tr, tc, tr+halfSize-1, tc+halfSize-1, halfSize);
	}
	// 覆盖右上角子棋盘
	if(dr < tr+halfSize && dc >= tc+halfSize){
		// 特殊格在右上角
		chessBoard(tr, tc+halfSize, dr, dc, halfSize);
	} else {
		board[tr+halfSize-1][tc+halfSize]=tile;
		chessBoard(tr, tc+halfSize, tr+halfSize-1, tc+halfSize, halfSize);
	}
	// 覆盖左下角子棋盘
	if(dr >= tr+halfSize && dc < tc+halfSize){
		// 特殊格在左下角
		chessBoard(tr+halfSize, tc, dr, dc, halfSize);
	} else {
		board[tr+halfSize][tc+halfSize-1]=tile;
		chessBoard(tr+halfSize, tc, tr+halfSize, tc+halfSize-1, halfSize);
	}
	// 覆盖右下角子棋盘
	if(dr >= tr+halfSize && dc >= tc+halfSize){
		// 特殊格在右下角
		chessBoard(tr+halfSize, tc+halfSize, dr, dc, halfSize);
	} else {
		board[tr+halfSize][tc+halfSize]=tile;
		chessBoard(tr+halfSize, tc+halfSize, tr+halfSize, tc+halfSize, halfSize);
	}
}
void main(){
	int k, dr, dc;
	scanf("%d%d%d", &k, &dr, &dc);
	k = 1<<k;
	board[dr-1][dc-1] = 0;
	chessBoard(0, 0, dr-1, dc-1, k);
	for(int i=0; i<k; i++){
		for(int j=0; j<k; j++){
			printf("%-4d ", board[i][j]);
		}
		printf("\n");
	}
}

实现二：自己写的稍微和书中有点不一样

参数说明：

tr: 棋盘左上角行坐标
tc: 棋盘右上角列坐标
dr: 特殊格行坐标
dc: 特殊格列坐标
size: 规模大小
  1. 规模减半划分子问题
int halfSize = size / 2;
  1. 判断特殊块的位置
// 定义中间变量
int rmid = tr+halfSize-1;  // 行中间坐标
int cmid = tc+halfSize-1;  // 列中间坐标
int a[2], b[2], c[2], d[2];  // 特殊方格位置，分别为左上，右上，左下，右下

ps：横坐标 rmid 和纵坐标 cmid 标识左上子块的右下方格的坐标，如图：

image-20221022235028818

判断特殊方格是否在左上分块，在的话就给其余子块填充特殊块，并分别把特殊块的位置记录在 a, b, c, d 中

if(dr <= rmid && dc <= cmid){
    // 在左上
    board[rmid][cmid+1] = domino;
    board[rmid+1][cmid] = domino;
    board[rmid+1][cmid+1] = domino;
    a[0] = dr; a[1] = dc;
    b[0] = rmid; b[1] = cmid+1;
    c[0] = rmid+1; c[1] = cmid;
    d[0] = rmid+1; d[1] = cmid+1;
}

不在则判断是否在右上分块，在的话类似上面的步骤，略

else if(dr <= rmid && dc > cmid){
    // 在右上
    board[rmid][cmid] = domino;
    board[rmid+1][cmid] = domino;
    board[rmid+1][cmid+1] = domino;
    a[0] = rmid; a[1] = cmid;
    b[0] = dr; b[1] = dc;
    c[0] = rmid+1; c[1] = cmid;
    d[0] = rmid+1; d[1] = cmid+1;
}

不在则判断是否在左下分块，略

else if(dr > rmid && dc <= cmid){
    // 在左下
    board[rmid][cmid] = domino;
    board[rmid][cmid+1] = domino;
    board[rmid+1][cmid+1] = domino;
    a[0] = rmid; a[1] = cmid;
    b[0] = rmid; b[1] = cmid+1;
    c[0] = dr; c[1] = dc;
    d[0] = rmid+1; d[1] = cmid+1;
}

不在则判断是否在右下分块，略

else if(dr > rmid && dc > cmid){
    // 在右下
    board[rmid][cmid] = domino;
    board[rmid][cmid+1] = domino;
    board[rmid+1][cmid] = domino;
    a[0] = rmid; a[1] = cmid;
    b[0] = rmid; b[1] = cmid+1;
    c[0] = rmid+1; c[1] = cmid;
    d[0] = dr; d[1] = dc;
}
  1. 改变骨牌类型
// 骨牌类型变化
domino++;
  1. 递归

​ 按左上，右上，左下，右下的顺序递归，起始点坐标位置分别为 tr, tc， tr, cmid+1， rmid+1, tc， rmid+1, cmid+1

chessBoard(tr, tc, a[0], a[1], halfSize);
chessBoard(tr, cmid+1, b[0], b[1], halfSize);
chessBoard(rmid+1, tc, c[0], c[1], halfSize);
chessBoard(rmid+1, cmid+1, d[0], d[1], halfSize);

代码：

#include<stdio.h>

int domino = 1;  // 当前骨牌标识
int board[1024][1024];  // 棋盘

/**
* tr: 棋盘左上角行坐标
* tc: 棋盘右上角列坐标
* dr: 特殊格行坐标
* dc: 特殊格列坐标
* size: 规模大小
*/
void chessBoard(int tr, int tc, int dr, int dc, int size){
	// 边界条件，规模为1时
	if(size == 1){
		return;
	}
	int halfSize = size / 2;
	// 判断特殊方格位置
	int rmid = tr+halfSize-1;  // 行中间坐标
	int cmid = tc+halfSize-1;  // 列中间坐标
	
	int a[2], b[2], c[2], d[2];  // 特殊方格位置，分别为左上，右上，左下，右下
	
	if(dr <= rmid && dc <= cmid){
		// 在左上
		board[rmid][cmid+1] = domino;
		board[rmid+1][cmid] = domino;
		board[rmid+1][cmid+1] = domino;
		a[0] = dr; a[1] = dc;
		b[0] = rmid; b[1] = cmid+1;
		c[0] = rmid+1; c[1] = cmid;
		d[0] = rmid+1; d[1] = cmid+1;
	} else if(dr <= rmid && dc > cmid){
		// 在右上
		board[rmid][cmid] = domino;
		board[rmid+1][cmid] = domino;
		board[rmid+1][cmid+1] = domino;
		a[0] = rmid; a[1] = cmid;
		b[0] = dr; b[1] = dc;
		c[0] = rmid+1; c[1] = cmid;
		d[0] = rmid+1; d[1] = cmid+1;
	} else if(dr > rmid && dc <= cmid){
		// 在左下
		board[rmid][cmid] = domino;
		board[rmid][cmid+1] = domino;
		board[rmid+1][cmid+1] = domino;
		a[0] = rmid; a[1] = cmid;
		b[0] = rmid; b[1] = cmid+1;
		c[0] = dr; c[1] = dc;
		d[0] = rmid+1; d[1] = cmid+1;
	} else if(dr > rmid && dc > cmid){
		// 在右下
		board[rmid][cmid] = domino;
		board[rmid][cmid+1] = domino;
		board[rmid+1][cmid] = domino;
		a[0] = rmid; a[1] = cmid;
		b[0] = rmid; b[1] = cmid+1;
		c[0] = rmid+1; c[1] = cmid;
		d[0] = dr; d[1] = dc;
	}
	// 骨牌类型变化
	domino++;
	// 递归分治
	chessBoard(tr, tc, a[0], a[1], halfSize);
	chessBoard(tr, cmid+1, b[0], b[1], halfSize);
	chessBoard(rmid+1, tc, c[0], c[1], halfSize);
	chessBoard(rmid+1, cmid+1, d[0], d[1], halfSize);
}

void main(){
	int k, dr, dc;
	scanf("%d%d%d", &k, &dr, &dc);
	k = 1<<k;
	board[dr-1][dc-1] = 0;
	chessBoard(0, 0, dr-1, dc-1, k);
	for(int i=0; i<k; i++){
		for(int j=0; j<k; j++){
			printf("%-4d ", board[i][j]);
		}
		printf("\n");
	}
}
# 算法
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

软考中级-软件设计师 UML图详解（ 类图，对象图，用例图，序列图，通信图，状态图，活动图，构件图，部署图）

avatar 2048 AI社区
cover

机器学习 决策树-分类

avatar 2048 AI社区
cover

【SD教程】超详细AI绘画提示词语法讲解！

avatar 2048 AI社区