首页 > 代码库 > hdu2612(bfs)
hdu2612(bfs)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2612
题意:求2个点到任意一个KFC的距离之和,使其最小。
分析:由两个点出发分别两次bfs,求得到每个KFC的距离,再枚举每个KFC求得最小距离和即可。刚开始以为KFC不能通过,wa了一次,坑。。。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;int n,m;char s[210][210];int vis[210][210];int step1[210][210],step2[210][210];struct node{ int x,y;};int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};int judge(int x,int y){ return x>=0&&x<n&&y>=0&&y<m&&s[x][y]!=‘#‘;}void bfs(int x,int y,int flag){ queue<node>que; memset(vis,0,sizeof(vis)); node cur,nxt; cur.x=x;cur.y=y; que.push(cur); vis[x][y]=1; while(!que.empty()) { cur=que.front();que.pop(); int xx=cur.x,yy=cur.y; for(int i=0;i<4;i++) { int a=xx+dx[i],b=yy+dy[i]; if(judge(a,b)&&!vis[a][b]) { if(flag) step1[a][b]=step1[xx][yy]+1; else step2[a][b]=step2[xx][yy]+1; vis[a][b]=1; nxt.x=a,nxt.y=b; que.push(nxt); } } }}int main(){ int x,y,a,b; while(scanf("%d%d",&n,&m)>0) { for(int i=0;i<n;i++) scanf("%s",s[i]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(s[i][j]==‘Y‘) { x=i;y=j; } if(s[i][j]==‘M‘) { a=i;b=j; } } memset(step1,0,sizeof(step1)); memset(step2,0,sizeof(step2)); bfs(x,y,0);bfs(a,b,1); int ans=inf; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(s[i][j]==‘@‘&&step1[i][j]&&step2[i][j]) { ans=min(ans,step1[i][j]+step2[i][j]); } } printf("%d\n",ans*11); }}
hdu2612(bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。