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

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

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

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

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

4
注意：同一个位置最多可以走8次。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
typedef struct nn
{
    int x,y;
}poit;
typedef struct nnn
{
    int man[2],xz[2];
    int step;
}node;
int map[10][10],n,m,dir[4][2]={0,-1,0,1,-1,0,1,0};
int locte(node a)//反回人和箱的相对位置
{
    if(a.man[0]==a.xz[0])
    {
        if(a.man[1]==a.xz[1]+1) return 1;//人在箱的右边
        if(a.man[1]==a.xz[1]-1) return 1<<1;//人在箱的左边
    }
    else if(a.man[1]==a.xz[1])
    {
        if(a.man[0]==a.xz[0]+1) return 1<<2;//人在箱的下方
       if(a.man[0]==a.xz[0]-1) return 1<<3;//人在箱的上方
    }
    return 0;
}
void bfs(int &ok,node a)//人移动，找出从人的位置可以到箱的四个方位，以ok来压缩可以推的位置
{
    poit p1,p2;
    queue<poit>q;
    int vist[10][10]={0};
    p1.x=a.man[0]; p1.y=a.man[1];//起点
    vist[p1.x][p1.y]=1;
    q.push(p1);
    while(!q.empty())
    {
        p1=q.front(); q.pop();
        for(int i=0;i<4;i++)
        {
            p2.x=p1.x+dir[i][0]; p2.y=p1.y+dir[i][1];
            if(p2.x==a.xz[0]&&p2.y==a.xz[1])//箱的位置
            {
                a.man[0]=p1.x; a.man[1]=p1.y;
                ok|=locte(a);//压缩可到达的位置
                if(ok==15)return ;
            }
           else if(p2.x>=0&&p2.x<n&&p2.y>=0&&p2.y<m&&!vist[p2.x][p2.y]&&!map[p2.x][p2.y])
            {
                vist[p2.x][p2.y]=1; q.push(p2);
            }
        }
    }
}
int BFS(node a,poit end)//箱子移动
{
    int vist[10][10]={0},ok,x,y;
    queue<node>q;
    node b;
    vist[a.xz[0]][a.xz[1]]++; a.step=0;
    q.push(a);
    while(!q.empty())
    {
        a=q.front(); q.pop();
        ok=locte(a); bfs(ok,a);//找出可以推箱位置
        for(int i=0;i<4;i++)//向左推，右推，上推，下推 四个方向
        if(ok&(1<<i))
        {
            x=a.xz[0]+dir[i][0]; y=a.xz[1]+dir[i][1];
            if(x>=0&&x<n&&y>=0&&y<m&&vist[x][y]<9&&!map[x][y])//每个位置可以重复走，但最多走8次，每个方向2次
            {
                if(x==end.x&&y==end.y)//推到了指定的位置
                return a.step+1;
                b.man[0]=a.xz[0]; b.man[1]=a.xz[1];
                b.xz[0]=x; b.xz[1]=y; b.step=a.step+1;
                vist[x][y]++;//到达的次数加1
                q.push(b);
            }
        }
    }
    return -1;//不能推到指定位置
}
int main()
{
    int t;
    poit end;//指定要推到的位置
    node a;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j]==4)
            a.man[0]=i,a.man[1]=j,map[i][j]=0;//记录下来后，清0
            else if(map[i][j]==2)
            a.xz[0]=i,a.xz[1]=j,map[i][j]=0;
            else if(map[i][j]==3)
            end.x=i,end.y=j,map[i][j]=0;
        }
        printf("%d\n",BFS(a,end));
    }
}