NOI - OpenJudge - 2.5基本算法之搜索 - 2753:走迷宫 - 超级无敌详细题解（含多个不同算法AC代码）

点赞关注吧~

2753:走迷宫

• 查看
• 提交
• 统计
• 提问

总时间限制: 

1000ms

内存限制: 

65536kB

描述

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

输入

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用'.'表示，有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

样例输入

5 5
..###
#....
#.#.#
#.#.#
#.#..

样例输出

9

标准代码及题解

解题
简单的使用bfs或者dfs即可，因为R和C比较小，使用dfs也不会太消耗时间

代码
dfs
①平常做法，找时将地图某值设墙，找完后再设置路

（1）标准

#include <iostream>
using namespace std;
char map[45][45];
int R, C, ans = -1;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(int x, int y, int step) {if (x == R - 1 && y == C - 1 && (step < ans || ans == -1)) ans = step;int xx, yy;for (int i = 0; i < 4; i++) {xx = x + dir[i][0];yy = y + dir[i][1];if (xx >= 0 && xx < R && yy >= 0 && yy < C && map[xx][yy] == '.') {map[xx][yy] = '#';dfs(xx, yy, step + 1);map[xx][yy] = '.';}}
}
int main() {cin >> R >> C;for (int i = 0; i < R; i++)for (int j = 0; j < C; j++)cin >> map[i][j];dfs(0, 0, 1);cout << ans;
}

（2）本人手写

//DFS 做法
#include <bits/stdc++.h>
using namespace std;
int r,c;//r行 c列
int maze[45][45];
int ans=-1;
int movex[4]{-1,1,0,0};//上下左右
int movey[4]{0,0,-1,1};//上下左右
void dfs(int x,int y,int step){if(x==r&&y==c&&(step<ans||ans==-1)){ans=step;}for(int i=0;i<4;i++){int X,Y;X=x+movex[i];Y=y+movey[i];if(X>0&&X<=r&&Y>0&&Y<=c&&maze[X][Y]==0){maze[X][Y]=1;dfs(X,Y,step+1);maze[X][Y]=0;}}
}
int main(){cin>>r>>c;char node;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>node;if(node=='#'){maze[i][j]=1;}else if(node=='.'){maze[i][j]=0;}}}dfs(1,1,1);//dfs(x,y,step)cout<<ans<<endl;return 0;
}

②将路径设值，如果到某处以前到过且经过的长度较小则直接略过，进行减枝，减少递归次数

#include <iostream>
using namespace std;
int R, C, map[45][45], dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  //map记录这点经过的最短步数
void dfs(int x, int y) {int xx, yy;for (int i = 0; i < 4; i++) {  //四方xx = x + dir[i][0], yy = y + dir[i][1];if (xx >= 0 && xx < R && yy >= 0 && yy < C && map[x][y] + 1 < map[xx][yy]) {map[xx][yy] = map[x][y] + 1;dfs(xx, yy);}}
}
int main() {cin >> R >> C;char temp;for (int i = 0; i < R; i++)for (int j = 0; j < C; j++) {cin >> temp;map[i][j] = (temp == '.') ? 1e9 : -1;}map[0][0] = 1;dfs(0, 0);cout << map[R - 1][C - 1];  // 步数存在了map里
}

bfs
以前总是不明白为什么bfs适合找最短路径，这次好好思考了一下，可以这样理解，
bfs是从一点出发，将其相邻的各点依次加入到队列之中，然后将其相邻的队列分别求它的相邻队列

如图所示，最外层的点无论选择何种路径，最短路径的长度是已经确定了的且相等

当遇到障碍物时它仍是一层一层的进行下去

如果目标正好在一层上，那么这层所代表的距离就是最短距离，
bfs是一层一层，一圈一圈进行下去的，如果你寻找的点正好在那一圈上最短距离也就求出了，不会存在有其它道路更短的情况，因为每一圈下去都是最短路径
比如如图

有两条路径可以到达，绿色和蓝色，其中绿色较短，蓝色较长，蓝色可能会先到蓝绿交点，但他不会把绿色的路堵住，去走上面的路，而是走绿色接下来的路，因为bfs总是去寻找最短的路，如图红色的路径。

现在表达还是有些混乱，之后再更新修补

①使用队列

#include <iostream>
#include <queue>
using namespace std;
int R, C, step[45][45], dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char map[45][45];
int main() {cin >> R >> C;for (int i = 0; i < R; i++) cin >> map[i];queue<int> q;q.push(0 * C + 0);step[0][0] = 1;while (!q.empty()) {int x = q.front() / C, y = q.front() % C;q.pop();for (int i = 0; i < 4; i++) {int xx = x + dir[i][0], yy = y + dir[i][1];if (map[xx][yy] == '.' && !step[xx][yy]) {q.push(xx * C + yy);step[xx][yy] = step[x][y] + 1;}}}cout << step[R - 1][C - 1];
}

②数组模拟队列
把队列数组设置的长些，出队列直接前面指向加一，不必真正删除  

#include <iostream>
using namespace std;
int R, C, queue[2000], step[45][45], dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char map[45][45];
int main() {cin >> R >> C;for (int i = 0; i < R; i++) cin >> map[i];step[0][0] = 1;queue[0] = 0 * C + 0;for (int i = 0, have = 0; i <= have; i++) {int x = queue[i] / C, y = queue[i] % C;for (int j = 0; j < 4; j++) {int xx = x + dir[j][0], yy = y + dir[j][1];if (map[xx][yy] == '.' && !step[xx][yy]) {queue[++have] = xx * C + yy;step[xx][yy] = step[x][y] + 1;}}}cout << step[R - 1][C - 1];
}