UVA – 1601 – The Morning after Halloween(双向BFS)

2018年2月26日 0 条评论 3 次阅读 0 人点赞

题目链接:UVA - 1601

题目大意:w*h网络上有在一张图中,以最少的步数将a,b,c移到对应的A,B,C上去。

                    其中,每个2x2的方格都有障碍并且不能两个小写字母同时占据一个格子。

题目分析:

                隐式图的路径查找问题。

                因为可以扩展的节点情况太大,可以采用双向BFS的办法

                既每次扩展时,正向搜索一次,反向搜索一次。

                每次以一层为单位

                相遇时返回最短路径

                注意建图时要把可以走的路径提取出来建立一个新的图

给出代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
inline int getID(int a,int b,int c)
{
    return (a<<16)|(b<<8)|c;
}
inline bool confict(int a1,int b1,int a2,int b2)
{
    return ((a2==b2)||(a1==b2&&b1==a2));
}
int dis[210][210][210];
int mark[210][210][210];
int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, -1, 1};
int  deg[210];
int  to[210][210];
int st[5];
int ed[5];
char s[20][20];
int w,h,n;
int bfs()
{
    queue<int> q1;
    queue<int> q2;
    q1.push(getID(st[0], st[1], st[2]));
    q2.push(getID(ed[0], ed[1], ed[2]));
    dis[st[0]][st[1]][st[2]] = 0;
    dis[ed[0]][ed[1]][ed[2]] = 1;
    mark[st[0]][st[1]][st[2]]=1;
    mark[ed[0]][ed[1]][ed[2]]=2;
    while(!q1.empty()||q2.empty())
    {
        int t1=q1.size();
        int t2=q2.size();
        while(t1--)
        {
            int u=q1.front();
            q1.pop();
            int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff;    //解码
            //  cout<<a<<" "<<b<<" "<<c<<endl;
            //if(a==ed[0]&&b==ed[1]&&c==ed[2])
            //     return dis[a][b][c];
            for(int i=0; i<deg[a]; i++)
            {
                int a1=to[a][i];
                for(int j=0; j<deg[b]; j++)
                {
                    int b1=to[b][j];
                    if(confict(a,b,a1,b1))
                        continue;
                    for(int k=0; k<deg[c]; k++)
                    {
                        //   cout<<i<<" "<<j<<" "<<k<<" *"<<endl;
                        int c1=to[c][k];
                        if(confict(a,c,a1,c1)||confict(b,c,b1,c1))
                            continue;
                        if(mark[a1][b1][c1]==0)
                        {
                            q1.push(getID(a1,b1,c1));
                            dis[a1][b1][c1]=dis[a][b][c]+1;
                            mark[a1][b1][c1]=1;
                        }
                        else if(mark[a1][b1][c1]==2)
                        {
                            return dis[a][b][c]+dis[a1][b1][c1];
                        }
                    }
                }
            }
        }
        while(t2--)
        {
            int u=q2.front();
            q2.pop();
            int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff;
            //  cout<<a<<" "<<b<<" "<<c<<endl;
            //if(a==ed[0]&&b==ed[1]&&c==ed[2])
            //     return dis[a][b][c];
            for(int i=0; i<deg[a]; i++)
            {
                int a1=to[a][i];
                for(int j=0; j<deg[b]; j++)
                {
                    int b1=to[b][j];
                    if(confict(a,b,a1,b1))
                        continue;
                    for(int k=0; k<deg[c]; k++)
                    {
                        //   cout<<i<<" "<<j<<" "<<k<<" *"<<endl;
                        int c1=to[c][k];
                        if(confict(a,c,a1,c1)||confict(b,c,b1,c1))
                            continue;
                        if(mark[a1][b1][c1]==0)
                        {
                            q2.push(getID(a1,b1,c1));
                            dis[a1][b1][c1]=dis[a][b][c]+1;
                            mark[a1][b1][c1]=2;
                        }
                        else if(mark[a1][b1][c1]==1)
                        {
                            return dis[a][b][c]+dis[a1][b1][c1];
                        }
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d%d\n",&w,&h,&n)&&n)
    {
        for(int i = 0; i < h; i++)
        {
            fgets(s[i], 20, stdin);
            // cout<<i<<endl;
        }
        int cnt=0,x[210],y[210],id[21][21];
        for(int i=0; i<h; i++)
            for(int j=0; j<w; j++)
                if(!(s[i][j]=='#'))
                {
                    x[cnt]=i;
                    y[cnt]=j;
                    id[i][j]=cnt;
                    if(islower(s[i][j]))
                        st[s[i][j]-'a']=cnt;
                    else if(isupper(s[i][j]))
                        ed[s[i][j]-'A']=cnt;
                    cnt++;
                }
        for(int i=0; i<cnt; i++)
        {
            deg[i]=0;
            for(int j=0; j<5; j++)
            {
                int nx=x[i]+dx[j];
                int ny=y[i]+dy[j];
                if(!(s[nx][ny]=='#'))
                {
                    to[i][deg[i]++]=id[nx][ny];
                }
            }
        }
        if(n <= 2)
        {
            deg[cnt] = 1;
            to[cnt][0] = cnt;
            st[2] = ed[2] = cnt++;
        }
        if(n <= 1)
        {
            deg[cnt] = 1;
            to[cnt][0] = cnt;
            st[1] = ed[1] = cnt++;
        }
        memset(dis,0,sizeof(dis));
        memset(mark,0,sizeof(mark));
        printf("%d\n",bfs());
    }
    return 0;
}

DLKKILL

这个人太懒什么东西都没留下

文章评论(0)