C++算法题：日历拼图（DFS回溯法）详细解析

问题分析与准备

日历拼图的输入是一个月份和一个日期（如12月3日）。系统需要在一个7x7的网格中，用8个不同的多米诺骨牌式拼图块（代表数字1-8），精确填充由该日期构成的轮廓区域。空白位置（用.表示）需保持原样。

确定目标形状的步骤如下：

• 月份标记：将月份的个位或十位数字放在网格的第一行对应位置。
• 日期标记：将日期的两个数字依次放置在后续的空位中。

例如，对于“12月3日”，需要在网格中预留出字符 '0'（作为占位符区分）的位置来代表这些数字，其他未占用的位置由1-8号拼图块填补。

C++ 实现步骤

第1步：定义基础拼图块数据

每种拼图块可以用一个4x4的二维字符数组表示。非点字符（如'1', '2'）代表占据，点字符 '.' 代表空心。

char a[9][5][5]={
	{{'.','.','.','.'},
	{'.','.','.','.'},
	{'.','.','.','.'},
	{'.','.','.','.'}},	
	// ... 此处省略部分初始化代码，实际包含1-8号块的定义 ...
};

第2步：实现图形的旋转与翻转

为了穷举每个拼图块在放置时的所有可能朝向，我们需要两种变换操作：

1. 左右翻转 (Flip)：交换每一行的左右对称元素。
2. 顺时针旋转 (Rotate)：将矩阵行列转置并反转列序，实现90度顺时针旋转。

通过交替执行翻转和旋转，可以从一个初始形状生成共8种独特的放置形态，存入 b[i][j] 数组中（i为拼图编号，j为形态序号）。

// 翻转函数：交换第j列与第3-j列的元素
void filp(char a[5][5]){
	for(int i=0;i<4;i++)	
		for(int j=0;j<2;j++){
			swap(a[i][j],a[i][3-j]);
		}	
}

// 旋转函数：顺时针90度
void rot(char a[5][5]){
	char b[5][5];
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++)
			b[i][j] = a[3-j][i];	
	}
		for(int i=0;i<4;i++)
	for(int j=0;j<4;j++) a[i][j] = b[i][j];
}

第3步：构建全局网格与边界判断

使用一个 char mp[8][8] 的全局数组作为拼图板。程序中设计了专门的判定函数 candown(x,y,i,j)，用于检查第 i 个拼图的第 j 个形态能否放置在坐标 (x,y) 处。

判定逻辑包括：

1. 范围检测：确保拼图边缘不超出网格界限。
2. 冲突检测：确保拼图占据的区域不与已有的数字字符或已放置的拼图块重叠。

bool candown(int x,int y,int i,int j){
	int sx = -1, sy = -1;
	// 寻找当前拼图形态的第一个有效坐标点
	for(int xx=0;xx<4;xx++)
		for(int yy=0;yy<4;yy++){
			if(b[i][j][xx][yy] != '.'){
				sx = xx;
				sy = yy;
				int kx =sx,ky= sy;
				// 遍历拼图的所有非空单元进行校验
				while(kx<4 && ky<4){
						int nx = x + kx-sx;
						int ny = y + ky-sy;
						if(b[i][j][kx][ky]!='.'){
							if(nx<0 || ny<0) return false;
							// 检查是否与已有内容冲突
							if(mp[nx][ny]!='.') return false;
							// 其他越界情况的特殊处理...
						}
						// 遍历位移逻辑
						if(ky==3){kx++,ky=0;} else ky++;
					}
				return true;
			}
		}
	return false;
}

第4步：执行放置与回溯撤销

放置操作 down 将拼图图案写入全局网格 mp；撤销操作 undown 将相应位置重置为 '.'。这两者是对称的线性扫描写入过程。

第5步：编写深度优先搜索(DFS)

这是解题的核心。我们使用一维索引 id 映射到网格坐标 (x, y)。DFS 的流程如下：

1. 跳过已占用格：如果当前位置已被月份/日期标记或其他拼图占据，直接跳到下一个格子。
2. 递归终止条件：当遍历完所有关键格子且成功放置了8个块时，打印网格并结束程序。
3. 尝试放置：遍历所有未使用的拼图块（vis[i]==false），尝试其所有8个形态。若 candown 返回真，则调用 down 放置，标记已使用，然后递归进入下一层 dfs(id+1)。
4. 回溯：递归返回后，必须执行 undown 清除痕迹，并将 vis[i] 重置为0，以便探索其他分支。

void dfs(int id){
	int x = id/7;
	int y = id%7;
	// 跳过无效路径
	if(x<2 && y==6){
		dfs(id+1);
	}
	// 成功到达终点，输出结果
	if(x==6 && y==3){
		// 打印网格逻辑...
		exit(0); // 找到一个解即可退出
	}
	if(mp[x][y]!='.') dfs(id+1);
	// 核心回溯循环
	for(int i=1;i<=8;i++){		
		if(!vis[i]){
			for(int j=1;j<=8;j++){
				if(candown(x,y,i,j)){
					down(x,y,i,j);
					vis[i] = 1;
					dfs(id+1);
					undown(x,y,i,j); // 回溯还原
					vis[i] = 0;
				}
			}	
		}
	}
}

完整代码整合与运行

将上述模块整合至 main 函数中。首先读取输入的月份 m 和日期 d，初始化网格 mp 以标记不可用区域（即日期占位符），随后预处理生成所有拼图的8种形态，最后启动 dfs(0)。

以上就是使用C++深度优先搜索解决日历拼图问题的详细内容，更多关于C++算法技巧的资料请关注本站其它相关文章！