推箱子

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

Sample Output

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; queue
      
       q; void Bfs() //对于箱子 广搜人能将箱子像哪个方向推 { queue
       
        qq; 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
           
            ?
            ?
            ?
            ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1401 Solitaire	下一篇：C++11新特性之 rvalue Reference(..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: