Input
代码语言：javascript复制10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#Output
22
代码：
代码语言：javascript复制#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> P;
queue<P> pos;
const int maxn = 100;
char maze[maxn][maxn];
using namespace std;
int N, M; //N, M分别代表行数和列数
int bx = -1, by = -1, ex = -1, ey = -1; //代表起点和终点
int d[maxn][maxn]; //储存各个点到起点的距离
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1}; //遍历四个方向
int vis[maxn][maxn];
const int INF = 0x3f3f3f3f;
int bfs()
{
pos.push(P(bx, by));
memset(vis, 0, sizeof(vis));
while(pos.size())
{
P p = pos.front();
pos.pop();
if(p.first == ex && p.second == ey)
break;
vis[p.first][p.second] = 1;
//遍历四个方向
for(int i = 0; i < 4; i )
{
int curx = p.first dx[i], cury = p.second dy[i];
if(curx >= 0 && curx < N && cury >= 0 && cury < M && !vis[curx][cury] && maze[curx][cury] != '#') //说明它还未放入过栈中
{
vis[curx][cury] = 1; //表示已经访问过
pos.push(P(curx, cury));
d[curx][cury] = d[p.first][p.second] 1;
}
}
}
return d[ex][ey];
}
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')
{
bx = i;
by = j;
d[i][j] = 0;
}
else
d[i][j] = INF;
if(maze[i][j] == 'G')
{
ex = i;
ey = j;
}
}
}
int ans = bfs();
if(ans != INF)
cout << ans << endl;
else
cout << "NO way!" << endl;
}
