推箱子

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 10 Accepted Submission(s) : 4

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 Input15 50 3 0 0 01 0 1 4 00 0 1 0 01 0 2 0 00 0 0 0 0 Sample Output4

Author

Ignatius.L & weigang Lee

思路：要判断人是不是可以从4到达箱子的位置2,而且不止判断一次,因为推动箱子一步后,人的位置也会改变,所以每次移动箱子前都要判断

所以这里要用两个搜索,当每朝着一个方向移动一步箱子的时候,就需要判断 从 此刻的 人位置能不能到达箱子反方向的那个位置(人只能推箱子,

不能拉什么的)  注意人在移动的时候箱子对于人来说也算障碍物,这里需要开一个visit的四维数组记录走过的位置,

 

#include 
      
       #include
       
        #include
        
         #include 
         
          using namespace std;int m,n;int map[8][8];int dir[4][2]={1,0,-1,0,0,1,0,-1};int visit[8][8][8][8];//标记走过的点int stx1,sty1;  //人的起点int stx2,sty2;  //箱子的起点int  mun;struct nodes{    int x;    int y;    int bx;    int by;    int ct;};nodes node1,node2;void bfs(){    mun=100000;    queue
          
             q;    while(!q.empty())        q.pop();    visit[node1.x][node1.y][node1.bx][node1.by]=0;    q.push(node1);    while(!q.empty())    {        node1=q.front();        q.pop();        for(int i=0; i<4; i++)        {            node2.x=node1.x+dir[i][0];            node2.y=node1.y+dir[i][1];            node2.bx=node1.bx;            node2.by=node1.by;            node2.ct=node1.ct;            if(node2.x<0||node2.x>=m||node2.y<0||node2.y>=n)  //越界                continue;            if(map[node2.x][node2.y]==1)   //墙                continue;            if(visit[node2.x][node2.y][node2.bx][node2.by]<=node1.ct)                continue;            if(node2.x==node1.bx&&node2.y==node1.by)            {                node2.bx=node1.bx+dir[i][0];                node2.by=node1.by+dir[i][1];                node2.ct=node1.ct+1;                if(node2.bx<0||node2.bx>=m||node2.by<0||node2.by>=n)  //越界                    continue;                if(map[node2.bx][node2.by]==1)   //墙                    continue;                if(map[node2.bx][node2.by]==3)                {                    if(node2.ct