HDU 1254 推箱子（BFS）

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

思路；

1.由于求的是箱子的路径，则通过bfs去找箱子的最短路径

2.由于是人推箱子，所以在找箱子的路径是，需要通过bfs去判断人能否推箱子到那个路径上。

要点（嵌套bfs）

bfs_box时，需注意：是否在界内，是否不为墙，是否人能到推它的相应位置，判重（判断人是否已经在这里推过箱子了，防止TLE）

bfs_per时，需注意：是否在界内，是否不为墙，判重（人是否已经走过这）

 1 #include<iostream>
 2 #include<queue> 
 3 #include<cstring>
 4 using namespace std;
 5 int room[10][10];//房间布置 
 6 int n,m,res;//行、列 ,res为最终结果 
 7 struct node
 8 {
 9     int x,y,step;//x,y为坐标，step指箱子走过的路 
10 }per,fin,box;//分别指人，终点，以及箱子 
11 bool pvis[10][10];//人能到的位置 
12 bool pbvis[10][10][10][10];//判重
13 int rx[]={0,0,1,-1};
14 int ry[]={1,-1,0,0};
15 void bfs_per()//找出人当前可以走的位置 
16 {
17     queue<node>qper;
18     memset(pvis,false,sizeof(pvis));
19     qper.push(per);
20     node cur,next;
21     while(!qper.empty())
22     {
23         cur=qper.front();
24         qper.pop();
25         pvis[cur.x][cur.y]=true;
26         for(int i=0;i<4;i++)
27         {
28             next.x=cur.x+rx[i];
29             next.y=cur.y+ry[i];
30             if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m)//在界内 
31             if(room[next.x][next.y]==0)//可走
32             if(!pvis[next.x][next.y])
33                     qper.push(next);
34         }
35     }
36 }
37 void bfs_box()//找出箱子可移动的最短路径 
38 {
39     queue<node>qbox;
40     qbox.push(box);
41     qbox.push(per);
42     node cur,next;
43     while(!qbox.empty())
44     {
45         cur=qbox.front();//box所在位置
46         qbox.pop();
47         per=qbox.front();//人的位置
48         qbox.pop();
49         if(cur.x==fin.x&&cur.y==fin.y)
50         {
51             if(res==-1||cur.step<res)
52             res=cur.step;
53             return ;
54         }
55         pbvis[cur.x][cur.y][per.x][per.y]=true;
56         room[cur.x][cur.y]=2;//箱子人是不能走的
57         bfs_per();//人可以到达的位置 
58         room[cur.x][cur.y]=0;//回溯
59         for(int i=0;i<4;i++)
60         {
61             next.x=cur.x+rx[i];
62             next.y=cur.y+ry[i];
63             next.step=cur.step+1;
64             if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m) //在界内
65             if(room[next.x][next.y]==0)//箱子位置可达
66                 if(pvis[cur.x-rx[i]][cur.y-ry[i]])//人能到箱子的反方向
67                     if(!pbvis[next.x][next.y][cur.x][cur.y])//判重防止TLE
68                         {
69                             qbox.push(next);//箱子当前的位置
70                             qbox.push(cur);// 人当前的位置 
71                         } 
72         }
73     }        
74 }
75 int main()
76 { 
77     int T;
78     cin>>T;
79     while(T--)
80     {
81         cin>>n>>m;
82         for(int i=0;i<n;i++)
83         for(int j=0;j<m;j++)
84         {
85             cin>>room[i][j];
86             if(room[i][j]==2)
87             box.x=i,box.y=j,box.step=0;//初始化 
88             else if(room[i][j]==3)
89             fin.x=i,fin.y=j,room[i][j]=0;//处理成可以走的地方 
90             else if(room[i][j]==4)
91             per.x=i,per.y=j,room[i][j]=0;
92         }
93         res=-1;
94         memset(pbvis,false,sizeof(pbvis));//都没有访问过 
95         bfs_box();
96         printf("%d
",res);
97     } 
98     return 0;
99 }