首页 > 代码库 > 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