hdu2612 Find a way(BFS)

题意大致是两个人Y 和 M 要去@（KFC）相聚，问他们相聚的最短时间。

思路：BFS。分成两个图，一个用bfs跑Y去所有可到达的@的最短路径，一个用bfs跑M去所有可到达的@的最短路径，分别记录下来，然后求后求和取最小值。有一点我没从题目中读出来，就是Y和M各自所占的地方是否可以互相到达，试了下不可以，也就是说对于Y来说，M相当于‘#’。

AC Code:

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int N = 300;
char s[N][N],c[N][N];
int d[100000],p[100000];
int s1,s2,e1,e2;
#define INF 0x3f3f3f3f
struct node
{
  int a,b;
  int step;
  node(){}
  node(int a,int b,int c):a(a),b(b),step(c){}
};
node tmp,rmp;
int dir[][2] = {{1,0},{-1,0},{0,-1},{0,1}};  int n,m;
void bfs()
{
    queue<node> Q1,Q2;vector<int> v1,v2;
    Q1.push(tmp);
    while(Q1.size())//求出Y到@的最短路径
    {
        tmp = Q1.front();
        Q1.pop();
        int a = tmp.a,b = tmp.b,step = tmp.step;
        for(int i = 0;i<4;++i){
            int x = a + dir[i][0],y = b + dir[i][1];
            if(s[x][y]=='.'){
                s[x][y] = '#';
                Q1.push(node(x,y,step+1));
            }
            else if(s[x][y] == '@'){
                s[x][y] = '#';
                d[(x-1)*m + y] = (step+1)*11;//记录下来
                Q1.push(node(x,y,step+1));//别忘了放进队列！！！
                v1.push_back((x-1)*m + y);
            }
        }
    }
    Q2.push(rmp);
    while(Q2.size())
    {
        rmp = Q2.front();
        Q2.pop();
        int a = rmp.a,b = rmp.b,step = rmp.step;
        for(int i = 0;i<4;++i){
            int x = a + dir[i][0],y = b + dir[i][1];
            if(c[x][y]=='.'){
                c[x][y] = '#';
                Q2.push(node(x,y,step+1));
            }
            else if(c[x][y] == '@'){
                c[x][y] = '#';
                Q2.push(node(x,y,step+1));
                v2.push_back((x-1)*m + y);
                p[(x-1)*m + y] = (step+1)*11;
            }
        }
    }
    int MIN = INF;//以下求到@最短距离，因为有的@可能某个人到不了，所以初始化为 -1
    for(int i = 0;i < v1.size();++i){
        if(p[v1[i]]==-1) continue;
        MIN = min(p[v1[i]]+ d[v1[i]],MIN);
    }
    for(int i = 0;i < v2.size();++i){
        if(d[v2[i]]==-1) continue;
        MIN = min(p[v2[i]] + d[v2[i]],MIN);
    }
    cout<<MIN<<endl;


}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif 

    while(cin>>n>>m)
    {
        int cnt = 0;
        for(int i = 1;i <= n;++i)
        {
            for(int j= 1;j <= m; ++j)
            {
                cin>>s[i][j];
                c[i][j] = s[i][j];
                if(c[i][j] == 'Y') s1 = i,s2 = j;
                else if(c[i][j] == 'M') e1 = i,e2 = j;
            }
        }
            memset(d,-1,sizeof (d));
            memset(p,-1,sizeof(p));
            tmp.a = s1,tmp.b = s2,tmp.step = 0;
            rmp.a = e1,rmp.b = e2,rmp.step = 0;
            s[e1][e2] = '#';//对于Y来说，M相当于墙
            s[s1][s2] = '#';
            c[s1][s2] = '#';//对于M来说，Y相当于墙
            c[e1][e2] = '#';
            bfs();
    }
}

最后

以上就是开放招牌为你收集整理的hdu2612 Find a way(BFS)的全部内容，希望文章能够帮你解决hdu2612 Find a way(BFS)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。