文章目录
- 数字接龙
- 【问题描述】
- 解题思路
- DFS
数字接龙
【问题描述】
小蓝最近迷上了一款名为《数字接龙》的迷宫游戏,游戏在一个大小为N × N 的格子棋盘上展开,其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下:
- 从左上角 (0, 0) 处出发,目标是到达右下角 (N − 1, N − 1) 处的格子,每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
- 对于路径经过的棋盘格子,按照经过的格子顺序,上面的数字组成的序列要满足:0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。
- 途中需要对棋盘上的每个格子恰好都经过一次(仅一次)。
- 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1),那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。
为了方便表示,我们对可以行进的所有八个方向进行了数字编号,如下图2 所示;因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示,如下图 1是一个迷宫示例,它所对应的答案就是:41255214。
现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径,输出字典序最小的那一个;如果不存在任何一条路径,则输出 −1。
【输入格式】
第一行包含两个整数 N、K。
接下来输入 N 行,每行 N 个整数表示棋盘格子上的数字。
【输出格式】
输出一行表示答案。如果存在答案输出路径,否则输出 −1。
【样例输入】
3 3
0 2 0
1 1 1
2 0 2
【样例输出】
41255214
【样例说明】
行进路径如图 1 所示。
【评测用例规模与约定】
对于 80% 的评测用例:1 ≤ N ≤ 5。
对于 100% 的评测用例:1 ≤ N ≤ 10,1 ≤ K ≤ 10。
解题思路
题目分析:
- 从左上角 (0, 0) 处出发,目标是到达右下角 (N − 1, N − 1) 处的格子,每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
- 对于路径经过的棋盘格子,按照经过的格子顺序,上面的数字组成的序列要满足:0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。
- 途中需要对棋盘上的每个格子恰好都经过一次(仅一次)。
- 如果有多条路径,输出字典序最小的那一个
- 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1),那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。
解题思路:
- 因为题目的数据范围较小,所以可以使用DFS,移动方向为8个方向
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
- 我们需要保证遍历顺序为
0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . .
g[x][y] == k - 1 && g[tx][ty] == 0) || g[tx][ty] == g[x][y] + 1
g[x][y] == k - 1 && g[tx][ty] == 0 || g[tx][ty] == g[x][y] + 1
:这是一个复合条件,用于检查当前格子 (x, y) 的值与目标格子 (tx, ty) 的值之间的关系是否满足游戏规则。具体来说:
g[x][y] == k - 1 && g[tx][ty] == 0
:如果当前格子的值等于 k - 1(即棋盘上数字的最大值),则目标格子的值必须为 0,这样才能保证数字序列的循环性。||
:逻辑或操作符,用于连接上述条件和下面的条件。两者满足一个即可g[tx][ty] == g[x][y] + 1
:如果当前格子的值不是 k - 1,则目标格子的值必须比当前格子的值大 1,这样才能保证数字序列是递增的。
- 设置一个cnt,如果
cnt=n*n
说明遍历了每个位置 - 在遍历8个方向时我们按0、1、2、3、4、5、6、7的顺序遍历就能得到最小字典序,并且用path数组保存,就能把路径输出
- 只有走对角线才会发生相交,我们设置一个st数组存储到达每个格子的方向,再进行判断
if (i == 1 && (st[x - 1][y] == 3 || st[x][y + 1] == 7))continue; // 从当前格子向右移动,检查是否与之前的路径交叉
if (i == 3 && (st[x + 1][y] == 1 || st[x][y + 1] == 5))continue; // 从当前格子向下移动,检查是否与之前的路径交叉
if (i == 5 && (st[x][y - 1] == 3 || st[x + 1][y] == 7))continue; // 从当前格子向左下移动,检查是否与之前的路径交叉
if (i == 7 && (st[x][y - 1] == 1 || st[x - 1][y] == 5))continue; // 从当前格子向左上移动,检查是否与之前的路径交叉
DFS
这段代码是一个基于深度优先搜索(DFS)的算法,用于解决一个特定的路径问题,其中需要考虑路径的字典序。下面是对代码的详细注释:
#include<bits/stdc++.h> // 引入整个标准库和C++ STL库
using namespace std; // 使用标准命名空间int g[11][11]; // 棋盘,存储每个格子的数字
int d[11][11]; // 访问标记,表示当前格子是否已访问
int st[11][11]; // 状态数组,存储到达每个格子的方向
vector<int> path; // 存储最终的路径// 移动方向的偏移量,dx 和 dy 分别表示 x 和 y 轴上的偏移
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};int n, k; // n 是棋盘的大小,k 是棋盘上数字的最大值bool dfs(int x, int y, int cnt) { // 深度优先搜索函数if (x == n - 1 && y == n - 1 && cnt == n * n) // 如果到达棋盘底部的最后一个格子,并且格子数量符合,返回 truereturn true;for (int i = 0; i < 8; i++) { // 遍历所有八个方向int tx = x + dx[i]; // 计算目标x坐标int ty = y + dy[i]; // 计算目标y坐标// 检查目标位置是否在棋盘内,未被访问,并且满足数字序列条件if (tx >= 0 && tx < n && ty >= 0 && ty < n && d[tx][ty] == 0 &&((g[x][y] == k - 1 && g[tx][ty] == 0) || g[tx][ty] == g[x][y] + 1)) {// 检查当前方向是否会导致路径交叉if (i == 1 && (st[x - 1][y] == 3 || st[x][y + 1] == 7))continue; // 从当前格子向右移动,检查是否与之前的路径交叉if (i == 3 && (st[x + 1][y] == 1 || st[x][y + 1] == 5))continue; // 从当前格子向下移动,检查是否与之前的路径交叉if (i == 5 && (st[x][y - 1] == 3 || st[x + 1][y] == 7))continue; // 从当前格子向左下移动,检查是否与之前的路径交叉if (i == 7 && (st[x][y - 1] == 1 || st[x - 1][y] == 5))continue; // 从当前格子向左上移动,检查是否与之前的路径交叉st[x][y] = i; // 记录当前格子的方向d[tx][ty] = 1; // 标记目标格子为已访问path.push_back(i); // 将方向编号添加到路径中if (dfs(tx, ty, cnt + 1)) // 递归搜索下一个位置return true; // 如果找到路径,则返回 truepath.pop_back(); // 回溯,移除路径中的最后一个方向编号d[tx][ty] = 0; // 回溯,重置目标格子的访问标记st[x][y] = -1; // 回溯,重置当前格子的方向}}return false; // 如果所有方向都不是解决方案,则返回 false
}int main() {cin >> n >> k; // 读取棋盘大小和数字的最大值for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> g[i][j]; // 填充棋盘}}// 检查棋盘右下角的数字是否为 k-1,如果不是,则无法形成合法路径,输出-1if (g[n - 1][n - 1] != k - 1) {cout << -1;return 0;}memset(st, -1, sizeof st); // 初始化状态数组,所有值设为 -1d[0][0] = 1; // 标记起始格子为已访问if (dfs(0, 0, 1)) { // 从(0, 0)开始深度优先搜索for (auto i : path) // 输出找到的路径cout << i;} else {cout << -1; // 如果没有找到路径,输出-1}return 0;
}
这段代码使用了深度优先搜索算法来找到一条合法的路径,它考虑了路径的唯一性和循环序列的要求。代码中还包含了避免路径交叉的逻辑。如果找到了一条合法路径,它会输出该路径的编号序列;如果没有找到,它会输出-1。
注意,代码中 memset(st, -1, sizeof st);
用于初始化 st
数组的所有元素为 -1
,表示没有格子被访问过。而 d[0][0] = 1;
则是标记起始格子 (0, 0)
为已访问。path
数组用来存储路径,以便在找到解决方案时输出。