UVA589 Pushing Boxes

题解 算法-搜索 省选/NOI-
题目链接 编辑文章

题意

在 $R\times C$ 的含障碍的图上把箱子从起点推到终点,人一开始在另一个起点,求人的最短路径。多组数据。

$R,C\le 20$

题解

显然箱子是连续移动的,但人有时需要绕一圈去箱子的背面,所以先对箱子做 $\text{bfs1}$ 。

保存一个五元组 $(b_x,b_y,m_x,m_y,now)$ ,表示当前箱子在 $(b_x,b_y)$ ,人在 $(m_x,m_y)$ ,操作序列为 $now$ 。每次枚举四个方向移动箱子,并得到人到箱子背面的路径,把序列合并后进行拓展。

人到箱子背面还需要一次搜索,记为 $\text{bfs2}$ 。记录一个三元组 $(m_{x2},m_{y2},now2)$ ,表示人在 $(m_{x2},m_{y2})$ ,当前序列为 $now2$ 。同样是枚举四个方向拓展。不过需要注意的是箱子所在的位置也要算成障碍物,所以在函数中记录一个 $(b_{x2},b_{y2})$ 表示箱子所在的位置,每次搜索都判断一下。

还有两个细节(就是我一开始没考虑到的):

  1. 人推完箱子后应该站在箱子之前的位置,而不是箱子背面
  2. 判重的两个数组vis[]vis2[]都要清0
#include<bits/stdc++.h>
#define T tuple<int,int,int,int,string>
#define TIE tie(bx,by,mx,my,now)
#define T2 tuple<int,int,string>
#define TIE2 tie(mx2,my2,now2)
#define mt make_tuple

using namespace std;

int n,m,bx,by,mx,my,stx,sty,edx,edy,stbx,stby,mx2,my2,kase;
int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1}; //四个方向
char s[25][25]; //图
char chb[4]={'S','E','N','W'},chm[4]={'s','e','n','w'}; //四个方向对应的操作
string now,now2;
bool vis[25][25][25][25],vis2[25][25];

inline string bfs2(int sx,int sy,int ex,int ey,int bx2,int by2);
inline string bfs1();

int main()
{
    while (~scanf("%d%d",&n,&m) && n && m)
    {
        for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                if (s[i][j]=='S') stx=i,sty=j; //人的起点
                else if (s[i][j]=='T') edx=i,edy=j; //箱子的终点
                else if (s[i][j]=='B') stbx=i,stby=j; //箱子的起点
            }
        }
        printf("Maze #%d\n",++kase);
        cout<<bfs1()<<"\n\n"; //题目有锅,要输出两个回车
    }
    return 0;
}

inline string bfs1() //搜索箱子的路径,主过程
{
    queue <T> q;
    q.push(mt(stbx,stby,stx,sty,""));
    memset(vis,0,sizeof(vis));
    vis[stbx][stby][stx][sty]=1;
    while (!q.empty())
    {
        TIE=q.front(); q.pop();
        for (int i=0;i<4;i++)
        {
            int tbx=bx+fx[i],tby=by+fy[i],tmx=bx-fx[i],tmy=by-fy[i]; //箱子推到(tbx,tby) ,人在箱子背面(tmx,tmy)
            if (tbx<1 || tbx>n || tby<1 || tby>m || tmx<1 || tmx>n || tmy<1 || tmy>m) continue; //越界
            if (s[tbx][tby]=='#' || s[tmx][tmy]=='#') continue; //是障碍
            if (vis[tbx][tby][tmx][tmy]) continue; //搜索过
            string bef=bfs2(mx,my,tmx,tmy,bx,by); //人到箱子背面的路径
            if (bef[0]=='L') continue; //人无法到达箱子背面
            vis[tbx][tby][tmx][tmy]=1;
            string nxt=now+bef+chb[i]; //下一个状态的搜索序列
            if (tbx==edx && tby==edy) return nxt; //到达终点
            q.push(mt(tbx,tby,bx,by,nxt)); //下一个状态,注意人站在箱子原来的位置
        }
    }
    return "Impossible."; //没有找到答案
}

inline string bfs2(int sx,int sy,int ex,int ey,int bx2,int by2) //搜索人到箱子背面的路径
{
    if (sx==ex && sy==ey) return ""; //不需移动
    queue <T2> q;
    q.push(mt(sx,sy,""));
    memset(vis2,0,sizeof(vis2));
    vis2[sx][sy]=1;
    while (!q.empty())
    {
        TIE2=q.front(); q.pop();
        for (int i=0;i<4;i++)
        {
            int tmx2=mx2+fx[i],tmy2=my2+fy[i]; //下一步人在(tmx2,tmy2)
            if (tmx2<1 || tmx2>n || tmy2<1 || tmy2>m) continue; //越界
            if (s[tmx2][tmy2]=='#' || (tmx2==bx2 && tmy2==by2)) continue; //是障碍物或者箱子
            if (vis2[tmx2][tmy2]) continue;
            vis2[tmx2][tmy2]=1;
            string nxt2=now2+chm[i]; //下一步的操作序列
            if (tmx2==ex && tmy2==ey) return nxt2; //到达目标
            q.push(mt(tmx2,tmy2,nxt2));
        }
    }
    return "L"; //无法到达
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。