首页 > 代码库 > HDU - 1254 - 推箱子

HDU - 1254 - 推箱子

2024-07-12 04:04:28   221人阅读

线上题目：

推箱子

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


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

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

 

 

Input
输入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2&lt;=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
 
　　中文题意不解释，做法是BFS,但是和普通的BFS有点不一样,先说一下我的思路。
　　对于一副地图，先保存下人和箱子以及终点，然后将可以走和不可以走的点都区分好。然后我们只需要记录的状态是人和箱子的位置以及步数，我们需要判重人和箱子的位子所表示的状态是否已经出现过了，当箱子到达了目标地点的时候我们就返回步数，否则就返回-1,但是这里我们需要保证输出的步数一定是最小的，我们需要注意的是如果只是用队列来实现的话，不一定能保证到达的时候一定是最近，因为中途会遇到墙壁什么的，同时人去找箱子的过程也需要考虑会不会影响，所以这里我们需要使用的是优先队列，优先级是当前所走的步数，步数小的优先，看起来有点像启发式搜索= =，但是不算很明显。
 
上代码：
 
  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <queue>  6 #include <vector>  7 #include <set>  8 #define INF (1<<30)  9 #define MAX 10 10 using namespace std; 11  12 typedef struct state{ 13     int by,bx; 14     int ry,rx; 15     int step; 16  17     bool operator < (const state& o)const{ 18         return step>o.step; 19     } 20  21     bool operator == (const state& o)const{ 22         return (by==o.by && bx==o.bx && ry==o.ry && rx==o.rx); 23     } 24  25 }state; 26  27 int cy[]={0,1,0,-1}; 28 int cx[]={-1,0,1,0}; 29 int minn; 30 int n,m; 31 int mp[MAX][MAX]; 32 int ey,ex; 33 vector<state> vv; 34 priority_queue<state> q; 35 int isok(state v){ 36     if(0<=v.ry && v.ry<n && 0<=v.rx && v.rx<m && mp[v.ry][v.rx]!=1){ 37         if(v.ry ==v.by && v.rx == v.bx) return -1; 38         return 1; 39     } 40     return 0; 41 } 42  43 bool isexist(state v){ 44     for(unsigned int i=0;i<vv.size();i++) if(vv[i] == v) return 1; 45     vv.push_back(v); 46     return 0; 47 } 48  49 bool canPush(state v,int dir){ 50     v.by+=cy[dir];    v.bx+=cx[dir]; 51     if(0<=v.by && v.by<n && 0<=v.bx && v.bx<m && mp[v.by][v.bx]==0) return 1; 52     return 0; 53 } 54  55 int bfs(){ 56     state u,v; 57     while(!q.empty()) q.pop(); 58     vv.clear(); 59     for(int i=0;i<n;i++) for(int j=0;j<m;j++) 60         if(mp[i][j]== 2){ 61             u.by = i; u.bx = j; mp[i][j] = 0; 62         }else if(mp[i][j] == 3){ 63             ey = i; ex = j;     mp[i][j] = 0; 64         }else if(mp[i][j] == 4){ 65             u.ry = i; u.rx= j;  mp[i][j] = 0; 66         } 67     u.step = 0; 68     q.push(u); 69     int co = 0; 70     while(!q.empty()){ 71         u = q.top(); 72         q.pop(); 73         co++; 74         for(int i=0;i<4;i++){ 75             v = u; 76             v.ry+=cy[i];    v.rx+=cx[i]; 77             int f = isok(v); 78             if(f == 0) continue; 79             else if(f == 1 && isexist(v)) continue; 80             else if(f == -1){ 81                  if(!canPush(v,i)) continue; 82                  v.by+=cy[i];   v.bx+=cx[i]; 83                  v.step++; 84                  if(v.by == ey && v.bx == ex){ return v.step ;} 85                  if(isexist(v)) continue; 86             } 87             q.push(v); 88         } 89     } 90     return -1; 91 } 92  93 int main() 94 { 95     int t; 96     //freopen("ans.txt","r",stdin); 97     scanf("%d",&t); 98     while(t--){ 99         scanf("%d %d",&n,&m);100         for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&mp[i][j]);101         int ans = bfs();102         printf("%d\n",ans);103     }104     return 0;105 }
1254

 

 


联系
我们