给你一个n行m列的二维迷宫。 'S' 表示起点, 'T' 表示终点, '#'表示墙壁,'.' 表示平地。你需要从 'S' 出发走到 'T',每次只能上下左右走动,并且不能走出地图的范围以及不能走到墙壁上。请你计算出走到终点需要走的最少步数。
第一行输入n,m表示迷宫大小。(100以内)
接下来输入n行字符串表示迷宫,每个字符串长度为m。(地图保证有且仅有一个终点,一个起始点)
输出走到终点的最少步数,如果不能走到终点输出-1,占一行。
2 3 S.# ..T
3
3 3 S.# .#. .#T样例输出2
-1
这道题同样是一道经典的BFS,对于bfs的描述,请详见:C++-BFS 广搜的含义 - 冯子坤 - 博客园 (cnblogs.com)
这道题如果使用char纯字符计算,不仅空间复杂度大,还随时可能TLE,因此,我们需要在输入时把他们转换一下……就像这样。
1 for (int i = 1; i <= n; i++) 2 for (int j = 1; j <= m; j++) { 3 char ip1; 4 cin >> ip1; 5 if (ip1 == 'S') { 6 bx = i; 7 by = j; 8 } else if (ip1 == '.') 9 a[i][j] = 1; 10 else if (ip1 == 'T') 11 a[i][j] = 2; 12 else 13 a[i][j] = 0; 14 }
这样转换成数字,后续写程序也要容易得多;
另外我们需要定义一个结构体,高度集成!
1 struct point { 2 int x; 3 int y; 4 point(int xx, int yy) 5 { 6 x = xx; 7 y = yy; 8 } 9 };
至于BFS代码吗……这里就是用伪代码来给大家理解吧:
void bfs(int sx, int sy) { // (sx, sy) 为搜索的起点 queue<point> q; q.push(point(sx, sy)); // 将起始点放入队列中 用vis数组标记(x, y)已经被访问过; while(队列非空) { 取出队列元素(x, y); for (枚举(x, y)能到达的所有格子(tx, ty)) { if (点(tx, ty)合法,可以搜索) { 标记(tx, ty)已经被访问过; 记录走到(tx, ty)的步数 = 走到(x, y)的步数 + 1; q.push(point(tx, ty)) } } } return; }
接下来就是把它们转换成真正代码了!;
#include <bits/stdc++.h> using namespace std; int a[105][105], mark[105][105], b[105][105]; int mn = 0; int chx[4] = {1, 0, -1, 0}; int chy[4] = {0, 1, 0, -1}; struct point { int x; int y; point(int xx, int yy) { x = xx; y = yy; } }; int bfs(int i, int j) { queue<point>q; q.push(point(i, j)); mark[i][j] = 1; while (!q.empty()) { i = q.front().x; j = q.front().y; q.pop(); for (int k = 0; k < 4; k++) { int tx = i + chx[k]; int ty = j + chy[k]; if (!mark[tx][ty] && a[tx][ty]) { mn = b[i][j] + 1; b[tx][ty] = mn; mark[tx][ty] = 1; if (a[tx][ty] == 2) return 1; else q.push(point(tx, ty)); } } } return 0; } int main() { int n, m; int bx, by; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { char ip1; cin >> ip1; if (ip1 == 'S') { bx = i; by = j; } else if (ip1 == '.') a[i][j] = 1; else if (ip1 == 'T') a[i][j] = 2; else a[i][j] = 0; } if (bfs(bx, by)) cout << mn; else cout << -1; return 0; }
使用此博客请标明出处!否则一律视为盗版!做人有底线!