本文主要是介绍hdu 2612 Find a way（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2612
题目大意：
Y与M到任意一个'@'所需最少时间。
思路：
两遍BFS计算出Y到任意一个’@‘的所需时间以及M到任意一个’@‘的所需时间，求和的最小值。
哎，挺简单的就是不知道最初写的哪有bug。
求bug。。T.T
正确代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
using namespace std;
const int MAXN=200+10;bool flag[MAXN][MAXN];
int sss[MAXN][MAXN][2];//两遍BFS的结果
char G[MAXN][MAXN];
int n,m;const int dir[][2]={{-1,0},{0,-1},{1,0},{0,1}};
bool check(int x,int y)
{if(x>=0&&x<n&&y>=0&&y<m&&G[x][y]!='#'&&!flag[x][y])return true;return false;
}struct node
{int x,y;int ss;
};void BFS(int x,int y,int s)
{memset(flag,0,sizeof(flag));flag[x][y]=true;queue<node>q;node pos,nextpos;pos.x=x;pos.y=y;pos.ss=0;q.push(pos);while(!q.empty()){pos=q.front();q.pop();nextpos.ss=pos.ss+1;for(int i=0;i<4;i++){int tx=pos.x+dir[i][0];int ty=pos.y+dir[i][1];if(check(tx,ty)){nextpos.x=tx;nextpos.y=ty;flag[tx][ty]=true;if(G[tx][ty]=='@')sss[tx][ty][s]=nextpos.ss;q.push(nextpos);}}}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){//memset(ss,0,sizeof(ss));//不知为何不能初始化为0for(int i=0;i<n;i++)for(int j=0;j<m;j++)sss[i][j][0]=sss[i][j][1]=1e5;for(int i=0;i<n;i++)scanf("%s",G[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(G[i][j]=='Y')BFS(i,j,0);else if(G[i][j]=='M')BFS(i,j,1);}int ans=1e5;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(G[i][j]=='@'&&ans>sss[i][j][0]+sss[i][j][1])ans=sss[i][j][0]+sss[i][j][1];printf("%d\n",ans*11);}return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
#include<map>
using namespace std;
const int MAXN=200+10;
char G[MAXN][MAXN];
bool flog[MAXN][MAXN];
int num;
int n,m;
typedef pair<int,int>ii;
const int nextpos[][2]={{1,0},{-1,0},{0,-1},{0,1}};map<int,int>kfc;bool check(int x,int y)
{if(x<0||x>=n||y<0||y>=m||G[x][y]=='#'||flog[x][y])return false;return true;
}void BFS(int x,int y)
{memset(flog,0,sizeof(flog));flog[x][y]=true;queue<ii>q;ii pos;pos.first=x*n+y;pos.second=0;q.push(pos);int s=0;while(!q.empty()){pos=q.front();q.pop();if(G[pos.first/n][pos.first%n]=='@'){kfc[pos.first]+=pos.second;s++;if(s==num)return;}for(int i=0;i<4;i++){int tempx=pos.first/n+nextpos[i][0];int tempy=pos.first%n+nextpos[i][1];if(check(tempx,tempy)){ii p;p.first=tempx*n+tempy;p.second=pos.second+1;flog[tempx][tempy]=true;q.push(p);}}}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){num=0;kfc.clear();int x1,y1,x2,y2;for(int i=0;i<n;i++){scanf("%s",G[i]);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(G[i][j]=='@'){kfc[i*n+j]=0;num++;}else if(G[i][j]=='Y'){x1=i;y1=j;}else if(G[i][j]=='M'){x2=i;y2=j;}}}BFS(x1,y1);BFS(x2,y2);int ans=1e5;for(map<int,int>::iterator it=kfc.begin();it!=kfc.end();it++){if(it->second<ans&&it->second!=0) ans=it->second;//cout<<it->second<<endl;}cout<<ans*11<<endl;}return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=200+10;
bool flog[MAXN][MAXN];
int step[MAXN][MAXN][2];
char G[MAXN][MAXN];
int n,m;
const int dir[][2]={{-1,0},{0,-1},{1,0},{0,1}};
bool check(int x,int y)
{if(x<0||x>=n|y<0||y>=m||G[x][y]=='#'||flog[x][y])return false;return true;
}
void BFS(int x,int y,int s)
{memset(flog,0,sizeof(flog));flog[x][y]=true;step[x][y][s]=0;queue<int>q;int pos=x*n+y;q.push(pos);while(!q.empty()){pos=q.front();q.pop();for(int i=0;i<4;i++){int tx=pos/n+dir[i][0];int ty=pos%n+dir[i][1];if(check(tx,ty)){step[tx][ty][s]=step[pos/n][pos%n][s]+1;flog[tx][ty]=true;q.push(tx*n+ty);}}}
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){//memset(step,0,sizeof(step));for(int i=0;i<n;i++)for(int j=0;j<m;j++)step[i][j][0]=step[i][j][1]=1e5;for(int i=0;i<n;i++)scanf("%s",G[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(G[i][j]=='Y')BFS(i,j,0);else if(G[i][j]=='M')BFS(i,j,1);}int ans=1e5;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(G[i][j]=='@'&&ans>step[i][j][0]+step[i][j][1])ans=step[i][j][0]+step[i][j][1];printf("%d\n",ans*11);}return 0;
}
这篇关于hdu 2612 Find a way（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
