【1254 HDU】推箱子（BFS）

傷城~ 2022-05-10 09:38 336阅读 0赞

题目：[点击打开题目链接][Link 1]

**Problem Description**

推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M\*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.  
  
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.![c15-1004-1.jpg][]

**Input**

输入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2<=M,N<=7),代表房间的大小,然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置.

**Output**

对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1.

**Sample Input**

1  
5 5  
0 3 0 0 0  
1 0 1 4 0  
0 0 1 0 0  
1 0 2 0 0  
0 0 0 0 0

**Sample Output**

题目思路：要求箱子到达目的地最少移动的格数，而这道题是人推着箱子走的，所以除了考虑箱子的位置是否合理（判断是否超出房间以外而且箱子的位置不能是墙）之外，还要考虑人能否把箱子推到下一个位置，即考虑人是否能到达箱子的屁股后面（因为要想把箱子往前推一格，人必须在箱子的后面一格才能推箱子）这2个因素。因此，除了用一个bfs把箱子移动的格数求出来之外，还需要用一个bfs或dfs来判断人是否能到达箱子的屁股后面。还有就是这道题要注意箱子走过的地方还可以回来。

如果还是有点不明白的话可以看看下面的图。

假设起初箱子在X（蓝色）的位置，人在Y（蓝色）的位置，为了方便，我们就假设房间里没有墙，都可以走。

1.假设箱子的下一个位置是b的位置，那么人要想把箱子推到b的位置，人就得在P的位置才能把箱子推到b处，所以这个时候我们就要判断人是否能从Y的位置走到P的位置，而且在这个过程中，人不能穿过箱子的位置X走到P，即人不仅不能撞到墙，也不能撞到箱子

![70][]

2.因为这只走了4个方向中的一个方向，下面我们在判断箱子往右走的情况，同样也是除了判断箱子的下一个位置是否合理外，还要判断人是否能从Y走到P的位置，如图

![70 1][]

然后就这样以此类推，直到箱子走到目的地，不能到达就输出-1.

My DaiMa：

#include <iostream>
    #include<stdio.h>
    #include<malloc.h>
    #include<queue>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int n,m,flag[10][10];///n行m列，flag存的是房间里的数字
    int dir[4][2] = {
       {1,0},{-1,0},{0,1},{0,-1}};
    int vis[10][10][10][10];
    int mark[10][10];
    struct position
    {
        int bx,by,px,py,step;
    }start;
    bool judge(int cur_px,int cur_py,int nex_px,int nex_py,int cur_bx,int cur_by)
    {
        memset(mark,0,sizeof(mark));///人走过的地方以免重复，就不判断了，所以用到标记
        queue <position> q;
        position cur,nex;
        cur.px = cur_px;
        cur.py = cur_py;
        mark[cur.px][cur.py] = 1;
        q.push(cur);
        while(!q.empty())
        {
            cur = q.front();
            q.pop();
            if(cur.px == nex_px && cur.py == nex_py) return true;
            for(int i = 0; i < 4; i++)
            {
                nex.px = cur.px + dir[i][0];
                nex.py = cur.py + dir[i][1];
                if(nex.px == cur_bx && nex.py == cur_by) continue;///人的下一个位置不能是箱子的位置，因为人不能穿过箱子
                if((nex.px >= 0 && nex.px < n) && (nex.py >=0 && nex.py < m) && flag[nex.px][nex.py] != 1  && mark[nex.px][nex.py] != 1)
                {
                    mark[nex.px][nex.py] = 1;
                    q.push(nex);
                }
            }
        }
        return false;
    }
    int bfs()
    {
        memset(vis,0,sizeof(vis));
        start.step = 0;
        vis[start.bx][start.by][start.px][start.py] = 1;
        queue<position>Q;
        Q.push(start);
        position cur,nex;
        while(!Q.empty())
        {
            cur = Q.front();
            Q.pop();
            if(flag[cur.bx][cur.by] == 3) return cur.step;
            for(int i = 0; i < 4; i++)
            {
                nex.bx = cur.bx + dir[i][0];///人把箱子往前推一步，即箱子的下一个位置
                nex.by = cur.by + dir[i][1];
                nex.px = cur.bx - dir[i][0];///人要想把箱子往前推一步，那人就得在箱子的屁股后面
                nex.py = cur.by - dir[i][1];
    
                if(nex.px < 0 || nex.px >= n || nex.py < 0 || nex.py >= m || flag[nex.px][nex.py] == 1) continue;///判断人的位置是否合理
                if(nex.bx < 0 || nex.bx >= n || nex.by < 0 || nex.by >= m || flag[nex.bx][nex.by] == 1 || vis[nex.bx][nex.by][nex.px][nex.py] == 1) continue;///判断箱子的位置是否合理
                if(judge(cur.px,cur.py,nex.px,nex.py,cur.bx,cur.by))///判断人是否能到达箱子的后面
                {
                    nex.step = cur.step + 1;
                    vis[nex.bx][nex.by][nex.px][nex.py] = 1;
                    Q.push(nex);
                }
            }
        }
        return -1;
    }
    int main()
    {
        int t;
        cin >> t;
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    cin >> flag[i][j];
                    if(flag[i][j] == 2)
                    {
                        start.bx = i;
                        start.by = j;
                    }
                    if(flag[i][j] == 4)
                    {
                        start.px = i;
                        start.py = j;
                    }
                }
            }
            int ans;
            ans = bfs();
            cout << ans << endl;
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1254
[c15-1004-1.jpg]: /images/20220510/bd3941b0859448219f9afe598c0b857e.png
[70]: /images/20220510/93cac02c07604a0d891e8f80ae84b4e1.png
[70 1]: /images/20220510/af1587ec7ebf44f88f3da1412f38625f.png