首页 > 代码库 > hdu 1254（推箱子游戏bfs+状态标记）

hdu 1254（推箱子游戏bfs+状态标记）

2024-07-21 09:35:51   221人阅读

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1254

推箱子

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5181    Accepted Submission(s): 1439


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
题意:      如题就是推箱子，熟悉推箱子的规则即可；
思路：（1）这道题初看不好弄，后来学到了一种状态标记的方法，用一个数组vis[][][][]标记当前的状态，（状态包括当前人的位置，当前箱子的位置，当前的推箱子的步数）
            （2）因为在每一步的过程中可能会出现之前出现过的状态，所以得标记一下防止同样状态的节点入队；
            （3）优先队列优化~ 
            （4）细心才能AC~
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
int map[10][10];
int n,m,px,py,sx,sy,ex,ey;//设置全局变量,分别是人的初始位置，箱子的初始位置，箱子的终点位置
bool vis[10][10][10][10];//标志状态

int xx[]={0,0,-1,1};//设置方向数组优化广搜
int yy[]={-1,1,0,0};

struct node
{
 int px,py;//人的位置
 int sx,sy;
 int step;
 bool operator <(const node &p) const
 {
   return p.step<step;
 }
};

void bfs(int x,int y)
{
  memset(vis,false,sizeof(vis));
  priority_queue<node>que;
  node q,p;
  q.px=x;q.py=y;q.sx=sx;q.sy=sy;q.step=0;
  vis[q.px][q.py][q.sx][q.sy]=true;
  que.push(q);
  while(!que.empty())
  {
   q=que.top();
   que.pop();
   if(q.sx==ex&&q.sy==ey)
   {
      printf("%d\n",q.step);
      return;
   }
   for(int i=0;i<4;i++)
   {
       p.px=q.px+xx[i];
       p.py=q.py+yy[i];
       p.sx=q.sx;
       p.sy=q.sy;
       p.step=q.step;
       //判可行性
       if(p.px<1||p.px>n||p.py<1||p.py>m) continue;
       if(map[p.px][p.py]==1||vis[p.px][p.py][p.sx][p.sy]) continue;
       if(p.px==p.sx&&p.py==p.sy)//找到箱子，那么就沿着前进这个方向推
       {
           p.sx=p.sx+xx[i];
           p.sy=p.sy+yy[i];
           p.step+=1;
           //判可行性
           if(p.sx<1||p.sx>n||p.sy<1||p.sy>m)continue;
           if(map[p.sx][p.sy]==1||vis[p.px][p.py][p.sx][p.sy])continue;
       }
       que.push(p);
       vis[p.px][p.py][p.sx][p.sy]=true;
   }
  }
  printf("-1\n");
}

int main()
{
        int T;
        cin>>T;
        while(T--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
             for(int j=1;j<=m;j++)
             {
              scanf("%d",&map[i][j]);
              if(map[i][j]==2)
              {
                 sx=i;
                 sy=j;
                 //map[i][j]=0;
              }
              else if(map[i][j]==3)
              {
                 ex=i;
                 ey=j;
                // map[i][j]=0;
              }
              else if(map[i][j]==4)
              {
                 px=i;
                 py=j;
                // map[i][j]=0;
              }
             }
              bfs(px,py);
        }
        return 0;
}



hdu 1254（推箱子游戏bfs+状态标记）


联系
我们