HDU 2612 Find a way（BFS）

提交判断的链接 题目提交ＨＤＵ

HDU 或 HDOJ 2612 Find a way (两次 BFS)

#include <iostream> //结果正确，提交AC
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 210
int step1[maxn][maxn];
//记录Y走的步数
int step2[maxn][maxn];
//记录W走的步数
int visit[maxn][maxn];
//标记走过与否
char tu[maxn][maxn];
struct node{
//便于向队列中插入二维坐标
int x,y;
}st1,st2;
int dx[]={1,0,-1,0};
//指定四个方向（下右上左）
int dy[]={0,1,0,-1};
int n,m;
int check(int x,int y)
{
if(x<n && x>=0 && y<m && y>=0 && ! visit[x][y] && tu[x][y]!='#')
return 0;
return 1;
//代表越界
}
void BFS(node st,int step[][210])
//BFS的模板
{
queue<node>Q;
//BFS不同于DFS，BFS不用递归调用自己。while即可遍历全部
Q.push(st);
visit[st.x][st.y]=1;
while(!Q.empty()){
node t=Q.front();//固定格式，取值然后弹出
Q.pop();
for(int i=0;i<4;i++){
node temp;
temp.x = t.x + dx[i];
temp.y = t.y + dy[i];
if(check(temp.x , temp.y))//如果越界
continue;
Q.push(temp);
step[temp.x][temp.y]=step[t.x][t.y]+1;
//层数加一
visit[temp.x][temp.y]=1;
}
}
return ;
}
int main()
{
while(cin>>n>>m){
for(int i=0;i<n;i++){
scanf("%s",tu[i]);
for(int j=0;j<m;j++){
if(tu[i][j]=='Y'){
st1.x=i;st1.y=j;
}
if(tu[i][j]=='M'){
st2.x=i;st2.y=j;
}
}
}
memset(visit,0,sizeof(visit));
memset(step1,0,sizeof(step1));
BFS(st1,step1);
//向step1数组中存入数据
memset(visit,0,sizeof(visit));
memset(step2,0,sizeof(step2));
BFS(st2,step2);
//向step2数组中存入数据
int ans=maxn;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int t1 = step1[i][j];
int t2 = step2[i][j];
if(tu[i][j]=='@' && t1!=0 && t2!=0){
//求解过程
if(t1 +t2 < ans)
ans=t1+t2;
}
}
}
cout<<ans*11<<endl;
}
return 0;
}

最后

以上就是稳重眼神为你收集整理的HDU 2612 Find a way（BFS）的全部内容，希望文章能够帮你解决HDU 2612 Find a way（BFS）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。