贵阳市住房和城乡建设局政务网站,没人注意的暴利行业,中国建设质量协会网站,焦作网站建设公司哪家好我们来玩一个迷宫游戏#xff0c;尝试走一下面的迷宫。 迷宫游戏 我们用一个二维的字符数组来表示前面画出的迷宫#xff1a;
S**.
....
***T
其中字符S表示起点#xff0c;字符T表示终点#xff0c;字符*表示墙壁#xff0c;字符.表示平地。你需要从S出发走到T#xf…我们来玩一个迷宫游戏尝试走一下面的迷宫。 迷宫游戏 我们用一个二维的字符数组来表示前面画出的迷宫
S**.
....
***T
其中字符S表示起点字符T表示终点字符*表示墙壁字符.表示平地。你需要从S出发走到T每次只能向上下左右相邻的位置移动不能走出地图也不能穿过墙壁每个点只能通过一次。你需要编程来求解出一种从起点到终点的走法。
很明显当我们从任意格子出发都有可能往四个方向走上下左右。而初始的时候我们是在起点S处之后开始进行我们的搜索过程也就是我们要讲的 DFS 算法。
那么当我们搜索到了某一个格子也就是我们下一步会从该格子出发的时候
1.首先要判断一下当前格子是否就是终点如果是那么就表示我们已经成功的从起点S移动了若干步之后到达了终点T便成功地完成了这个问题。 2.否则我们就需要从该格子出发可以分别枚举向左、向下、向右、向上四个方向依次去判断它旁边的四个点是否可以作为下一步合法的目标点如果可以那么我们就进行这一步走到目标点然后继续进行操作。 3.当然有可能左、下、右、上四个点都无法再成为合法的目标点了那么我们就回退一步然后从上一步所在的那个格子向其他 未尝试的方向 继续枚举。
关于合法的定义如下
必须在所给定的迷宫范围内。 如样例中是一个 4 行 3 列的迷宫那么这个点必须在 (0,0)−(3,2) 的范围中才能称为合法否则即为不合法。
这个点在搜索过程中必须没有被访问过。 也就是说一个点在 DFS 的过程中只能被访问一次不能重复访问。这样做是因为如果一个点允许多次访问那么肯定会出现死循环的情况——在两个点中间来回走。不过根据题意在某些情况下你回溯了之后可以视回溯前的点为没有访问过。
这个点必须不是墙壁。这个显然很好理解我们只能走在平地上不能走在墙壁上也不能穿过墙壁。
DFS 走迷宫对应的伪代码框架如下
// 对坐标为 (x, y) 的点进行搜索
bool dfs(int x, int y) {if (x, y) 是终点 {// 找到了路径return true;}// 标记 (x, y) 已经访问// 向上走到位置 (tx, ty)if (tx, ty) 合法 {if (dfs(tx, ty) true) {// 递归调用 DFS 函数将(tx, ty)作为当前状态进行搜索下同。return true;}}// 向左走到位置 (tx, ty)if (tx, ty) /* 合法 */ {if (dfs(tx, ty) true) {return true;}}// 向下走到位置 (tx, ty)if (tx, ty) /* 合法 */ {if (dfs(tx, ty) true) {return true;}}// 向右走到位置 (tx, ty)if (tx, ty) /* 合法 */ {if (dfs(tx, ty) true) {return true;}}return false;
}
迷宫搜索2(输出路径
#include iostream
#include string
using namespace std;
int n, m;
string maze[110];
int sx, sy;
bool vis[110][110];
int dir[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool in(int x, int y) {return 0 x x n 0 y y m;
}
bool dfs(int x, int y) {vis[x][y] true;if (maze[x][y] T) {return true;}maze[x][y] m;for (int i 0; i 4; i) {int tx x dir[i][0];int ty y dir[i][1];if (in(tx, ty) !vis[tx][ty] maze[tx][ty] ! *) {if (dfs(tx, ty)) {return true;}}}maze[x][y] .;return false;
}
int main() {cin n m;for (int i 0; i n; i) {cin maze[i];}for (int i 0; i n; i) {for (int j 0; j m; j) {if (maze[i][j] S) {sx i;sy j;}}}if (dfs(sx, sy)) {cout Yes endl;} else {cout No endl;}for(int i 0; i n; i){cout maze[i] endl;}return 0;
}
