链接:https://ac.nowcoder.com/acm/contest/940/D
来源:牛客网
题目描述
kotori在一个n*m迷宫里,迷宫的最外层被岩浆淹没,无法涉足,迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的,最近的出口离她有多远?
输入描述:
第一行为两个整数n和m,代表迷宫的行和列数 (1≤n,m≤30)
后面紧跟着n行长度为m的字符串来描述迷宫。‘k’代表kotori开始的位置,’.‘代表道路,’*'代表墙壁,'e’代表出口。保证输入合法。
输出描述:
若有出口可以抵达,则输出2个整数,第一个代表kotori可选择的出口的数量,第二个代表kotori到最近的出口的步数。(注意,kotori到达出口一定会离开迷宫)
若没有出口可以抵达,则输出-1。
直接BFS求解即可
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<LL,LL>
#define PCC pair<char,char>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
const int N=1e3+7;
const int INF=1e8,mod=109;
char a[N][N];
int n,m;
int ans,cnt;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int b[N][N];
struct node{
int FI,SE,st;
};
void bfs(int x,int y){
ans=INF;
queue<node>q;
q.push(node{x,y,0});
b[x][y]=1;
while(!q.empty()){
node k=q.front();
q.pop();
if(a[k.FI][k.SE]=='e'){
cnt++;
ans=min(ans,k.st);
continue;
}
for(int i=0;i<4;i++){
node mid=node{k.FI+dx[i],k.SE+dy[i],k.st+1};
if(mid.FI>0&&mid.FI<=n&&mid.SE>0&&mid.SE<=m&&a[mid.FI][mid.SE]!='*'&&!b[mid.FI][mid.SE]){
q.push(mid);
b[mid.FI][mid.SE]=mid.st;
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='k'){
bfs(i,j);
if(cnt==0)cout<<-1;
else cout<<cnt<<' '<<ans;
return 0;
}
}
}
return 0;
}