首页 > 代码库 > HDU - 1254 - 推箱子
HDU - 1254 - 推箱子
线上题目:
推箱子
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<=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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。