用 a[N][N] 接收地图。
dis[N][N] 存储到每个点的路径长度。
从起点出发，广度优先遍历地图：
起点入队。
如果队列非空，一直执行下面语句：
- 队头出队。
- 遍历队头的上下左右四个方向：如果是 ‘.’ 走过去，并且该位置入队，该点对应的dis值更新为队头的dis + 1，该点更新为’#’,表示走过了。如果是 ‘#’ 不做处理，如果是 ‘E’,走到了终点，输出该点对应的 dis 值。
如果队列为空，还没有找到终点，则无法到达，输出 oop!。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 210;
char a[N][N];
int dis[N][N];
void bfs(PII start)
{
queue<PII> q;
q.push(start);//队头队，对应步骤1
while(!q.empty())
{
PII u = q.front();
q.pop();
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0 ,-1};
for(int i = 0; i < 4; i++)//遍历四个方向，对应步骤2
{
int x = u.first + dx[i];
int y = u.second + dy[i];
if(a[x][y] == '#') continue;//如果是'#',不做任何处理
if(a[x][y] == '.')//如果是 '.'，更新对应内容
{
dis[x][y] = dis[u.first][u.second] + 1;
a[x][y] = '#';
q.push({x, y});
}
if(a[x][y] == 'E')//如果是'E'，找到了，输出
{
cout << dis[u.first][u.second] + 1 << endl;
return;
}
}
}
cout << "oop!" << endl;//没有找到
}
int main()
{
int t;
cin >> t;
while(t--)
{
memset(a, '#', sizeof(a));//初始化地图，各个点都是墙。
memset(dis, 0, sizeof(dis));//初始化dis
int n,m;
PII start;
cin >> n >> m;
for(int i = 1; i <= n; i++)//从第一行存储地图，因为四周都是墙，bfs时，可以不做越界判断
{
for(int j = 1; j <= m; j++)//从第一；列存储地图，因为四周都是墙，bfs时，可以不做越界判断
{
cin >> a[i][j];
if(a[i][j] == 'S')//记录下起点位置。
start.first = i, start.second = j, a[i][j] = '#';
}
}
bfs(start);
}
}
说明一下，地图初始化为全是墙，然后把地图存储在a[1][1] ~ a[n][m]后，地图四周会被墙包围，所以 bfs 的时候，不用做地图越界处理了。
求点赞~
有问题直接评论即可。
思路好清晰，比y总的还要好理解
如果是使用PII ,记得数组是 N*N
太强了，是个思路，太华丽了这想法，不过我想不到，还是这种判断边界的丑陋想法适合我
为什么能保证答案最小？
如果有两条路的话，万一走的是较长的那条路呢？
感觉要让队列走完，并且记录每一条能走到E的路径的长度，然后取最小值吧
因为是一层一层搜的，先找到就是最短的
感谢！你说的没错。我之前已经想明白了，因为队列先进先出，一层一层，而不是深搜
优雅！！！
memset(a, ‘#’, sizeof(a));
为什么 地图还要初始化，明明每回都会覆盖
如果第二次输入的r和c比第一次输入的小，那么就影响了
写得很简洁， 思路清晰， 新手很喜欢， 谢谢大佬
大佬好强
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=1001;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
bool st[N][N];
int r,c;
char map1[1000][1000];
struct node
{int x;
int y;
}start,end;
int res;
queue[HTML_REMOVED] q;
bool judge(int x,int y)
{
if(x>0&&x<=r&&y>0&&y<=c&&st[x][y]==false&&map1[x][y]!=’#’)
return true;
else
return false;
}
int bfs(int x,int y)
{
q.push(start);
st[start.x][start.y]=true;
while(q.size()!=0)
{
node temp=q.front();
q.pop();
if(map1[temp.x][temp.y]==’E’)
return res;
for(int i=0;i<4;i)
{
int nx=temp.x+dx[i];
int ny=temp.y+dy[i];
if(judge(nx,ny))
{node temp1;
temp1.x=nx;
temp1.y=ny;
st[nx][ny]=true;
q.push(temp1);
}
}
res;
}
return -1;}
int main()
{int n;
cin>>n;
while(n–)
{
cin>>r>>c;for(int i=1;i<=r;i)
{
for(int j=1;j<=c;j)
{
cin>>map1[i][j];
if(map1[i][j]==’S’)
start.x=i,start.y=j;
if(map1[i][j]==’E’)
end.x=i,end.y=j;
}
}
res=bfs(start.x,start.y);
if(res==-1)
printf(“oop!\n”);
else
printf(“%d\n”,res);
memset(st,false,sizeof st);
memset(map1,’ ‘,sizeof map1);
res=0;
}
return 0;}
为什么我答案不对啊
为什么都是用的bfs,我的就tle了呢（哭辽）
请问下这个怎么保证是最短路径的呢
BFS最先输出的肯定是最短的，因为是按宽度搜索的
懂了谢谢hh
大佬不理解，如果有两条路的话，万一走的是较长的那条路呢？
感觉要让队列走完，并且记录每一条能走到E的路径的长度，然后取最小值吧
%%%%，好清晰的思路
qs好清晰呀
思路好清晰啊orz
已经定义全局变量了，dis[][]是不是可以不用memset
如果用一次，默认全部是0，可以不memset,这道题目要使用多次，所以要memset
啊，对对对