hdu 1254 推箱子 – pblr

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有用到了dfs太经典了。用bfs搜索箱子移动的最短距离,用dfs搜索人能否走到箱子后面。
 
1 #include<cstdio>
2 #include<cstring>
3 #include<queue>
4 using namespace std;
5 int m,n,ax,bx,ex,ey,flag,flog;
6 int s[23][23],s1[23][23][4],s2[23][23];
7 int yi[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
8 struct p
9 {
10 int x1,y1,x2,y2,t;
11 };p f,r;
12 void ff()
13 {
14 int i,j;
15 for (i=0;i<n;i++)
16 for (j=0;j<m;j++)
17 s2[i][j]=s[i][j];
18 flog=0;
19 }
20 int dfs(int x,int y)
21 {
22 if (flog) return flog;
23 if (x==f.x1&&y==f.y1) return flog=1;
24 if (x==r.x2&&y==r.y2) return 0;
25 int i,rx,ry;
26 for (i=0;i<4;i++)
27 {
28 rx=x+yi[i][0];
29 ry=y+yi[i][1];
30 if (rx>=0&&rx<n&&ry>=0&&ry<m&&s2[rx][ry]!=1)
31 {
32 s2[rx][ry]=1;
33 int k=dfs(rx,ry);
34 }
35 }
36 return flog;
37 }
38 int main()
39 {
40 int c,i,j,x2,x1,y1,y2;
41 scanf(%d,&c);
42 while (c–)
43 {
44 scanf(%d%d,&n,&m);
45 for (i=0;i<n;i++)
46 for (j=0;j<m;j++)
47 {
48 scanf(%d,&s[i][j]);
49 if (s[i][j]==3) {ex=i;ey=j;}
50 if (s[i][j]==4) {x1=i;y1=j;}
51 if (s[i][j]==2) {x2=i;y2=j;}
52 }
53 memset(s1,0,sizeof(s1));
54 flag=-1;
55 f.x1=x1;f.x2=x2;
56 f.y1=y1;f.y2=y2;
57 f.t=0;
58 queue<p>q;
59 q.push(f);
60 while (!q.empty())
61 {
62 r=q.front();
63 q.pop();
64 if (r.x2==ex&&r.y2==ey) {flag=r.t;break;}
65 for (i=0;i<4;i++)
66 {
67 f.x2=r.x2+yi[i][0];
68 f.y2=r.y2+yi[i][1];
69 f.x1=r.x2+yi[(i+2)%4][0]; //i+2表示箱子后面
70 f.y1=r.y2+yi[(i+2)%4][1];
71 if (f.x2>=0&&f.x2<n&&f.y2>=0&&f.y2<m&&!s1[f.x2][f.y2][i]&&s[f.x2][f.y2]!=1) //判断箱子下一步是否合法。
72 {
73 ff();
74 if (f.x1>=0&&f.x1<n&&f.y1>=0&&f.y1<m&&s[f.x1][f.y1]!=1&&dfs(r.x1,r.y1)) //判断人能否走到箱子后面
75 {
76 s1[f.x2][f.y2][i]=1;
77 f.t=r.t+1;
78 q.push(f);
79 }
80 }
81 }
82 }
83 printf(%dn,flag);
84 }
85 return 0;
86 }

 

本文链接:hdu 1254 推箱子,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量