首页 > 代码库 > Hdu2612Find a way bfs
Hdu2612Find a way bfs
题意: 两人任选一家 kfc店 ,然后两人走去那里,求可以选择的kfc店使得两人走的距离和最短。
分别以俩人 为原点跑遍bfs, 刚开始 maxn 开到222 挂了,然后改成333 就过了。。。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;const int INF=0xfffffff;const int maxn=222;int n,m;int bx,by,ex,ey;int vis[maxn][maxn];int dis[maxn][maxn];int Hash[maxn][maxn];int d[maxn][maxn];int sum;int gg[maxn*maxn];char str[maxn][maxn];int gaomaoxian(int x,int y){ if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&str[x][y]!=‘#‘) return 1; return 0;}int dx[]={0,0,-1,1};int dy[]={-1,1,0,0};void gao(){ memset(vis,0,sizeof(vis)); dis[bx][by]=0; for(int i=0;i<sum;i++) d[1][i]=INF; vis[bx][by]=1; queue<int> q; q.push(bx*m+by); while(!q.empty()){ int cur=q.front(); q.pop(); int xx=cur/m;int yy=cur%m; if(str[xx][yy]==‘@‘){ d[1][Hash[xx][yy]]=dis[xx][yy],vis[xx][yy]=1;gg[Hash[xx][yy]]=1; } for(int i=0;i<4;i++){ int x1=xx+dx[i];int y1=yy+dy[i]; if(!gaomaoxian(x1,y1)) continue; vis[x1][y1]=1; dis[x1][y1]=dis[xx][yy]+1; q.push(x1*m+y1); } }}void gao1(){ memset(vis,0,sizeof(vis)); for(int i=0;i<sum;i++) dis[2][i]=INF; dis[ex][ey]=0; vis[ex][ey]=1; queue<int> q; q.push(ex*m+ey); while(!q.empty()){ int cur=q.front();q.pop(); int xx=cur/m;int yy=cur%m; if(str[xx][yy]==‘@‘){ d[2][Hash[xx][yy]]= dis[xx][yy],vis[xx][yy]=1; gg[Hash[xx][yy]]=1; } for(int i=0;i<4;i++){ int x1=xx+dx[i];int y1=yy+dy[i]; if(!gaomaoxian(x1,y1)) continue; vis[x1][y1]= 1; dis[x1][y1]=dis[xx][yy]+1; q.push(x1*m+y1); } }}int main(){ while(cin>>n>>m){ int sum=0; memset(gg,0,sizeof(gg)); for(int i=0;i<n;i++){ scanf("%s",str[i]); for(int j=0;j<m;j++){ if(str[i][j]==‘M‘){ bx= i; by=j; } if(str[i][j]==‘Y‘){ ex=i;ey=j; } if(str[i][j]==‘@‘){ Hash[i][j]=sum++; } } } gao();gao1(); int ans= INF; for(int i=0;i<sum;i++){ if(!gg[i]) continue; int ans1=d[1][i]+d[2][i]; // printf("%d %d\n",d[1][i],d[2][i]); ans= min(ans,ans1); } cout<<ans*11<<endl; } return 0;}
Hdu2612Find a way bfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。