题目：点击打开题目链接

Problem Description

推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.

现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.

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

4

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

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

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

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

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

然后就这样以此类推，直到箱子走到目的地，不能到达就输出-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;
    }
}