数字接龙（蓝桥杯）
数字接龙【问题形貌】
小蓝近来迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为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
。
https://i-blog.csdnimg.cn/blog_migrate/64e2497649446ddb762989fdcad27a38.png
现在请你帮小蓝规划出一条行进路径并将其输出。假如有多条路径，输出字典序最小的那一个；假如不存在任何一条路径，则输出 −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 == k - 1 && g == 0) || g == g + 1
g == k - 1 && g == 0 || g == g + 1：这是一个复合条件，用于检查当前格子 (x, y) 的值与目标格子 (tx, ty) 的值之间的关系是否满足游戏规则。详细来说：
[*]g == k - 1 && g == 0：假如当前格子的值等于 k - 1（即棋盘上数字的最大值），则目标格子的值必须为 0，这样才气保证数字序列的循环性。
[*]||：逻辑或操作符，用于毗连上述条件和下面的条件。两者满足一个即可
[*]g == g + 1：假如当前格子的值不是 k - 1，则目标格子的值必须比当前格子的值大 1，这样才气保证数字序列是递增的。
[*]设置一个cnt，假如cnt=n*n说明遍历了每个位置
[*]在遍历8个方向时我们按0、1、2、3、4、5、6、7的顺序遍历就能得到最小字典序，并且用path数组生存，就能把路径输出
[*]只有走对角线才会发生相交，我们设置一个st数组存储到达每个格子的方向，再进行判定
https://i-blog.csdnimg.cn/blog_migrate/4cc9f9576b863162aad61b82ba491873.png
if (i == 1 && (st
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]