本文主要是介绍HDU 2612 水BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
两个人（Y和M）要在‘@’处相遇，图中有不定个‘@’；
对每个人做一遍BFS即可，然后枚举每个‘@’位置
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;
const int inf=0x7fffffff;
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node
{int x,y,t;
};int y_n,y_m,m_n,m_m,n,m;
char str[210][210];
int sum[210][210],mark[210][210];int Min(int a,int b)
{if (a<b) return a;else return b;
}int judge(int x,int y)
{if (x<0 || y<0 || x>=n || y>=m) return 0;if (mark[x][y]==1) return 0;if (str[x][y]=='#') return 0;return 1;
}void bfs()
{queue<node>q,qq;node cur,next;int i;cur.x=y_n;cur.y=y_m;cur.t=0;memset(mark,0,sizeof(mark));mark[y_n][y_m]=1;sum[cur.x][cur.y]=0;q.push(cur);while (!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (judge(next.x,next.y)==0) continue;next.t=cur.t+1;mark[next.x][next.y]=1;sum[next.x][next.y]=next.t;q.push(next);}}cur.x=m_n;cur.y=m_m;cur.t=0;memset(mark,0,sizeof(mark));mark[m_n][m_m]=1;qq.push(cur);while(!qq.empty()){cur=qq.front();qq.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (judge(next.x,next.y)==0) continue;next.t=cur.t+1;mark[next.x][next.y]=1;sum[next.x][next.y]+=next.t;qq.push(next);}}
}
int main()
{int i,j,ans;while (scanf("%d%d",&n,&m)!=EOF){for (i=0;i<n;i++)scanf("%s",str[i]);for (i=0;i<n;i++)for (j=0;j<m;j++)if (str[i][j]=='Y'){y_n=i;y_m=j;}elseif (str[i][j]=='M'){m_n=i;m_m=j;}memset(sum,-1,sizeof(sum));bfs();ans=inf;for (i=0;i<n;i++)for (j=0;j<m;j++)if (str[i][j]=='@' && sum[i][j]!=-1)ans=Min(ans,sum[i][j]);printf("%d\n",ans*11);}return 0;
}
这篇关于HDU 2612 水BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
