【算法】数字接龙 走迷宫问题的一般处理思路

前言

其实走迷宫就是一个普普通通的深搜+回溯嘛，但是我之前做的很多题都是在一个二维的地图上，只能上下左右四个方向走迷宫，在做数字接龙这道题的时候，相当于可以往8个方向走，虽然逻辑上不变，但按照我之前的处理方式，代码写的非常乱。

题目信息

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为N × N 的格子棋盘上展开，其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下：

1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N − 1, N − 1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。

3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。

4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 所示；因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示，如下图 1是一个迷宫示例，它所对应的答案就是：41255214。

现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

题目解析

本题要求我们按照一定顺序走完整个迷宫，从中可以得到两个条件
1、按照顺序走
2、走完迷宫

同时我们还发现，这个迷宫可以向8个方向走，这就可能引发一个新问题：不能交叉

3、不能交叉

细节：
1、要求我们按照字典序最小的排列，只要在第一次符合条件时，一定是字典序最小的，因为我们遍历方向数组是从0-7逐渐深搜+回溯的，第一次符合即是结果。

2、回溯的时候，可以利用传参的性质，在dfs函数上多加一个参数s，而不是对全局字符串±操作，这样更方便。

参考代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 15;
int dx[] = {-1, -1 , 0 , 1 ,1 ,1 , 0 ,-1};
int dy[] = {0 , 1 , 1 , 1 ,0 , -1,-1, -1};
int n, k;
string res, s;
int vis[N][N] , a[N][N];

void dfs(int x, int y, string s) {
	if (x == n && y == n && s.size() == (n*n)-1) {
		if (res.empty()) {
			res = s;
			return;
		}
	}

	for (int i = 0; i < 8; i++) {
		int bx = x + dx[i];
		int by = y + dy[i];
		if (bx < 1 || bx > n || by < 1 || by > n) continue;
		if (vis[bx][by] == true) continue;

		if (i == 1 && vis[x-1][y] && vis[x][y+1]) continue;
		else if (i == 3 && vis[x][y+1] && vis[x+1][y]) continue;
		else if (i == 5 && vis[x+1][y] && vis[x][y-1]) continue;
		else if (i == 7 && vis[x][y-1] && vis[x-1][y]) continue;



      if((a[x][y] < k-1 && a[bx][by] == a[x][y] +1) || (a[x][y] == k-1 && a[bx][by] == 0)){
			vis[bx][by] = true;
			dfs(bx, by, s + to_string(i));
			//剪枝
			if (!res.empty()) return; 
			vis[bx][by] = false;                       
		}
	}
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	vis[1][1] = true;
	dfs(1, 1, s);
	if (res.empty()) cout << -1 << endl;
	else cout << res << endl;
	return 0;
}