A8站源码交易平台 查找 Find a way HDU - 2612 BFS
题意：
两个人Y和M要去同一家肯德基吃饭，然后问你怎么走所花费的总时刻最少。
‘#’代表的是墙不能走。
思路：
便是广搜开两个数组，虽然在同一个行列里边，可是符号一下之后更新与他相关的相关数组就能够了。我wa了几回，最终必定要注意 有可能以有一家kfc是被包围在墙面里边的不可能抵达，所以要对能够抵达的kfc做一下符号。
其他便是bfs的板子套一下就能够了。
最终输出的是两个人抵达同一家店的时刻总和。记住乘11啊。A8站源码交易平台
ac代码：
#include
#include
#include
#include
#include
using namespace std;
char map[205][205];
int dis1[205][205]; //dis1和vis1处理的是Y走的状况
int vis1[205][205];
int dis2[205][205]; //dis2和vis2处理的是M走的状况
int vis2[205][205];
int map1[205][205]; //用来符号这家kfc究竟能不能到
int go[8]={1,0,-1,0,0,1,0,-1};
struct node{
int x,y,v; //v能够用来表明这个节点现在是谁在走1代表Y 2代表M。
};
queueq;
void bfs(int nn,int mm){
node now,temp;
while(!q.empty()){
//cout<<45<<endl;
now=q.front();
q.pop();
if(map[now.x][now.y]=='@'){
map1[now.x][now.y]=1;
}
for(int i=0;i<8;i+=2){
int xx=now.x+go[i];
int yy=now.y+go[i+1];
if(xx>=1&&xx<=nn&&yy>=1&&yy<=mm&&map[xx][yy]!='#'){
if(now.v==1&&!vis1[xx][yy]){
dis1[xx][yy]=dis1[now.x][now.y]+1;
temp.x=xx;temp.y=yy;temp.v=1;
q.push(temp);
vis1[xx][yy]=1;
}
if(now.v==2&&!vis2[xx][yy]){
dis2[xx][yy]=dis2[now.x][now.y]+1;
temp.x=xx;temp.y=yy;temp.v=2;
q.push(temp);
vis2[xx][yy]=1;
}
}
}
}
return ;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
while(!q.empty())q.pop();
memset(dis1,0,sizeof(dis1));
memset(dis2,0,sizeof(dis2));
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
memset(map1,0,sizeof(map1));
for(int i=1;i<=n;i++){
scanf("%s",map[i]+1);
}
node Y,M;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(map[i][j]=='Y'){
Y.x=i;Y.y=j;Y.v=1;
vis1[i][j]=1;
q.push(Y);
}
if(map[i][j]=='M'){
M.x=i;M.y=j;M.v=2;
vis2[i][j]=1;
q.push(M);
}
}
}
bfs(n,m);
int minn=0x3fffffff;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(map1[i][j]&&map[i][j]=='@'&&dis1[i][j]+dis2[i][j]<=minn){ //记住判别能不能到
//cout<<dis1[i][j]
}
}
}
printf("%d
",minn*11);
