推箱子

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

Total Submission(s) : 12 Accepted Submission(s) : 6

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

Author Ignatius.L & weigang Lee

 

推箱子，雙向廣搜，記錄每一個箱子狀態和對應人所在位置狀態

三維數組標記 記錄箱子在x,y點向i方向是否推過

 

 

#include
#include
#include
#include
using namespace std;

int Map[8][8];
bool vis[8][8][4],us[8][8];//標記箱子推過的方向  人走過的點
int dir[4][2]={0,1,0,-1,1,0,-1,0};
struct node
{
    int x,y;
    int xx,yy;
    int t;
}st,ed;
struct edg
{
    int x,y;
}a,b;
int n,m;
queueq;

void Bfs()  //對於箱子  廣搜人能將箱子像哪個方向推
{
    queueqq;
    memset(us,false ,sizeof(us));
    qq.push(a);
    while(qq.size())
    {
        a=qq.front();
        qq.pop();
        for(int i=0;i<4;i++)
        {
            int xx,yy;
            xx=a.x+dir[i][0];
            yy=a.y+dir[i][1];
            if(xx>=0&&xx=0&&yy=0&&x=0&&y