#include<bits/stdc++.h>
using namespace std;
int row,col;
int start_x,start_y,exit_num=0;
typedef pair<int,int> PII;
const int N=35;
char a[N][N];//记录地图
int step[N][N];//记录走到(N,N)时用的步数
vector<int> ans;//记录走到每个出口时所用的步数
queue<PII> q;
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};//上,下,左,右
void bfs(){
memset(step,-1,sizeof step);//将步数数组初始化为-1
q.push({start_x,start_y});
step[start_x][start_y]=0;
while (q.size())
{
auto t=q.front();q.pop();
for(int i =0;i<4;i++){
int tx=t.first+dx[i];int ty=t.second+dy[i];
//边界判断
if(tx<1||tx>row||ty<1||ty>col||a[tx][ty]=='*'||a[tx][ty]=='k') continue;
if(step[tx][ty]!=-1) continue;
step[tx][ty]=step[t.first][t.second]+1;//到达该位置的步数是上一步的步数+1
//检测到出口的情况
if(a[tx][ty]=='e') {
exit_num++;
ans.push_back(step[tx][ty]);
continue;
}
q.push({tx,ty});
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>row>>col;
for(int i = 1;i <= row;i++){
for(int j = 1;j <= col;j++){
cin>>a[i][j];
}
}
//遍历寻找开始位置
for(int i = 1;i <= row;i++){
for(int j = 1;j <= col;j++){
if(a[i][j]=='k'){
start_x=i,start_y=j;
}
}
}
bfs();
//记得判断是否找到出口
if(exit_num>0)
cout<<exit_num<<" "<<ans[0];//ans[0]代表第一个找到的出口,由于bfs的特性,他肯定是最短路径的出口
else cout<<-1;
return 0;
}
我自己其实觉得写的有点复杂了,希望有大佬指出可优化的地方
全部评论
(0) 回帖