首页 技术 正文

ＵＶＡ－１６０１　The Morning after Halloween（ＢＦＳ或双向BFS）

技术 2022年11月10日
0 收藏 943 点赞 4,545 浏览 6037 个字

题目大意：在一张图中，以最少的步数将a,b,c移到对应的A,B,C上去。其中，每个2×2的方格都有障碍并且不能两个小写字母同时占据一个格子。

题目分析：为避免超时，先将图中所有能联通的空格建起一张图，然后再BFS。

代码如下：

# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;struct Node
{
    int t,now[3];
    Node(int _t,int a=-1,int b=-1,int c=-1):t(_t){now[0]=a,now[1]=b,now[2]=c;}
    bool operator < (const Node &a) const {
        return t>a.t;
    }
};
struct Edge
{
    int to,nxt;
};
Edge e[2000];
char mp[17][17];
int w,h,n,cnt,head[267];
int goal[3],start[3],vis[268][268][268];
int d[5][2]={{0,0},{-1,0},{1,0},{0,1},{0,-1}};void add(int u,int v)
{
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}void init()
{
    cnt=0;
    memset(start,-1,sizeof(start));
    memset(goal,-1,sizeof(goal));
    memset(head,-1,sizeof(head));
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(mp[i][j]=='#')
                continue;
            if(mp[i][j]>='a'&&mp[i][j]<='c')
                start[mp[i][j]-'a']=i*w+j;
            if(mp[i][j]>='A'&&mp[i][j]<='C')
                goal[mp[i][j]-'A']=i*w+j;
            for(int k=0;k<5;++k){
                int ni=i+d[k][0],nj=j+d[k][1];
                if(ni>=0&&ni<h&&nj>=0&&nj<w&&mp[ni][nj]!='#')
                    add(i*w+j,ni*w+nj);
            }
        }
    }
}bool ok(const Node &u)
{
    for(int i=0;i<n;++i)
        if(u.now[i]!=goal[i])
            return false;
    return true;
}int bfs()
{
    priority_queue<Node>q;
    memset(vis,0,sizeof(vis));
    vis[start[0]+10][start[1]+10][start[2]+10]=1;
    q.push(Node(0,start[0],start[1],start[2]));
    while(!q.empty())
    {
        Node u=q.top();
        q.pop();        if(ok(u))
            return u.t;
        if(n==1){
            for(int i=head[u.now[0]];i!=-1;i=e[i].nxt){
                Node nxt=u;
                nxt.now[0]=e[i].to;
                if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10])    continue;
                vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=1;
                nxt.t=u.t+1;
                q.push(nxt);
            }
        }else if(n==2){
            for(int i=head[u.now[0]];i!=-1;i=e[i].nxt){
                Node nxt=u;
                nxt.now[0]=e[i].to;
                for(int j=head[u.now[1]];j!=-1;j=e[j].nxt){
                    nxt.now[1]=e[j].to;
                    if(nxt.now[0]==nxt.now[1])  continue;
                    if(nxt.now[0]==u.now[1]&&nxt.now[1]==u.now[0])    continue;
                    if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10])    continue;
                    vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=1;
                    nxt.t=u.t+1;
                    q.push(nxt);
                }
            }
        }else{
            for(int i=head[u.now[0]];i!=-1;i=e[i].nxt){
                Node nxt=u;
                nxt.now[0]=e[i].to;
                for(int j=head[u.now[1]];j!=-1;j=e[j].nxt){
                    nxt.now[1]=e[j].to;
                    if(nxt.now[0]==nxt.now[1])  continue;
                    if(nxt.now[0]==u.now[1]&&nxt.now[1]==u.now[0])    continue;
                    for(int k=head[u.now[2]];k!=-1;k=e[k].nxt){
                        nxt.now[2]=e[k].to;
                        if(nxt.now[2]==nxt.now[0]||nxt.now[2]==nxt.now[1])  continue;
                        if(nxt.now[2]==u.now[0]&&nxt.now[0]==u.now[2])  continue;
                        if(nxt.now[2]==u.now[1]&&nxt.now[1]==u.now[2])  continue;
                        if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10])    continue;
                        vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=1;
                        nxt.t=u.t+1;
                        q.push(nxt);
                    }
                }
            }
        }
    }
}int main()
{
    while(scanf("%d%d%d",&w,&h,&n)&&(w+h+n))
    {
        getchar();
        for(int i=0;i<h;++i)
            gets(mp[i]);
        init();
        printf("%d\n",bfs());
    }
    return 0;
}

　　

这道题已知结束状态，还可以使用双向BFS（个人感觉使用双向BFS的效率提升的并不是多明显，从2002ms提到1189ms，也可能是我的代码写得比较挫吧！！！）。

代码如下：

# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;struct Node
{
    int t,now[3];
    Node(int _t,int a=-1,int b=-1,int c=-1):t(_t){now[0]=a,now[1]=b,now[2]=c;}
    bool operator < (const Node &a) const {
        return t>a.t;
    }
};
struct Edge
{
    int to,nxt;
};
Edge e[2000];
char mp[17][17];
int w,h,n,cnt,head[267],mark[268][268][268];
int goal[3],start[3],vis[268][268][268];
int d[5][2]={{0,0},{-1,0},{1,0},{0,1},{0,-1}};
priority_queue<Node>q[2];void add(int u,int v)
{
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}void init()
{
    cnt=0;
    memset(start,-1,sizeof(start));
    memset(goal,-1,sizeof(goal));
    memset(head,-1,sizeof(head));
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(mp[i][j]=='#')
                continue;
            if(mp[i][j]>='a'&&mp[i][j]<='c')
                start[mp[i][j]-'a']=i*w+j;
            if(mp[i][j]>='A'&&mp[i][j]<='C')
                goal[mp[i][j]-'A']=i*w+j;
            for(int k=0;k<5;++k){
                int ni=i+d[k][0],nj=j+d[k][1];
                if(ni>=0&&ni<h&&nj>=0&&nj<w&&mp[ni][nj]!='#')
                    add(i*w+j,ni*w+nj);
            }
        }
    }
}int bfs(int id,int step)
{
    while(!q[id].empty()){
        Node u=q[id].top();
        if(u.t!=step)
            return -1;
        q[id].pop();        if(n==1){
            for(int i=head[u.now[0]];i!=-1;i=e[i].nxt){
                Node nxt=u;
                nxt.now[0]=e[i].to;
                if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]==-1){
                    vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=id;
                    mark[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=u.t+1;
                    nxt.t=u.t+1;
                    q[id].push(nxt);
                }else if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]==!id)
                    return u.t+1+mark[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10];
            }
        }else if(n==2){
            for(int i=head[u.now[0]];i!=-1;i=e[i].nxt){
                Node nxt=u;
                nxt.now[0]=e[i].to;
                for(int j=head[u.now[1]];j!=-1;j=e[j].nxt){
                    nxt.now[1]=e[j].to;
                    if(nxt.now[0]==nxt.now[1])  continue;
                    if(nxt.now[0]==u.now[1]&&nxt.now[1]==u.now[0])    continue;
                    if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]==-1){
                        vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=id;
                        mark[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=u.t+1;
                        nxt.t=u.t+1;
                        q[id].push(nxt);
                    }else if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]==!id)
                        return u.t+1+mark[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10];
                }
            }
        }else{
            for(int i=head[u.now[0]];i!=-1;i=e[i].nxt){
            Node nxt=u;
                nxt.now[0]=e[i].to;
                for(int j=head[u.now[1]];j!=-1;j=e[j].nxt){
                    nxt.now[1]=e[j].to;
                    if(nxt.now[0]==nxt.now[1])  continue;
                    if(nxt.now[0]==u.now[1]&&nxt.now[1]==u.now[0])    continue;
                    for(int k=head[u.now[2]];k!=-1;k=e[k].nxt){
                        nxt.now[2]=e[k].to;
                        if(nxt.now[2]==nxt.now[0]||nxt.now[2]==nxt.now[1])  continue;
                        if(nxt.now[2]==u.now[0]&&nxt.now[0]==u.now[2])  continue;
                        if(nxt.now[2]==u.now[1]&&nxt.now[1]==u.now[2])  continue;
                        if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]==-1){
                            vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=id;
                            mark[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]=u.t+1;
                            nxt.t=u.t+1;
                            q[id].push(nxt);
                        }else if(vis[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10]==!id)
                            return u.t+1+mark[nxt.now[0]+10][nxt.now[1]+10][nxt.now[2]+10];
                    }
                }
            }
        }
    }
    return -1;
}int solve()
{
    while(!q[0].empty())
        q[0].pop();
    while(!q[1].empty())
        q[1].pop();
    memset(vis,-1,sizeof(vis));
    memset(mark,0,sizeof(mark));
    vis[start[0]+10][start[1]+10][start[2]+10]=0;
    vis[goal[0]+10][goal[1]+10][goal[2]+10]=1;
    q[0].push(Node(0,start[0],start[1],start[2]));
    q[1].push(Node(0,goal[0],goal[1],goal[2]));
    int step=0;
    while(!q[0].empty()||!q[1].empty()){
        if(!q[0].empty()){
            int k=bfs(0,step);
            if(k!=-1)
                return k;
        }
        if(!q[1].empty()){
            int k=bfs(1,step);
            if(k!=-1)
                return k;
        }
        ++step;
    }
    return -1;
}int main()
{
    while(scanf("%d%d%d",&w,&h,&n)&&(w+h+n))
    {
        getchar();
        for(int i=0;i<h;++i)
            gets(mp[i]);
        init();
        printf("%d\n",solve());
    }
    return 0;
}

　　

点赞 943

贡献者

上一篇： torchnet package (1)
下一篇： 124. Binary Tree Maximum Path Sum *HARD* -- 二叉树中节点和最大的路径的节点和
相关推荐
python开发_常用的python模块及安装方法
python开发_常用的python模块及安装方法
adodb：我们领导推荐的数据库连接组件bsddb3：BerkeleyDB的连接组件Cheetah-1.0：我比较喜欢这个版本的cheeta…
技术
日期：2022-11-24 点赞：878 阅读：9,147
Educational Codeforces Round 11 C. Hard Process 二分
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…
技术
日期：2022-11-24 点赞：807 阅读：5,618
下载Ubuntn 17.04 内核源代码
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
技术
日期：2022-11-24 点赞：569 阅读：6,461
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
技术
日期：2022-11-24 点赞：733 阅读：6,236
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…
技术
日期：2022-11-24 点赞：512 阅读：7,871
Struts的使用
Struts的使用
一、Struts2的获取　　Struts的官方网站为：http://struts.apache.org/　　下载完Struts2的jar包,…
技术
日期：2022-11-24 点赞：671 阅读：4,953
Lomu

贡献者

这家伙很懒，只想把你留下。

文章
141
收藏
0
人气
468,807
粉丝
进主页
文章展示
  • [ 技术 ] python开发_常用的python模块及安装方法
  • [ 技术 ] Educational Codeforces Round 11 C. Hard Process 二分
  • [ 技术 ] 下载Ubuntn 17.04 内核源代码
  • [ 技术 ] 可用Active Desktop Calendar V7.86 注册码序列号
  • [ 技术 ] Android调用系统相机、自定义相机、处理大图片
  • [ 技术 ] Struts的使用
    • 个人收藏笔记记录
    我的笔记
    首页 首页 菜单 首页 首页