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
Author
Ignatius.L & weigang Lee
思路；
1.由于求的是箱子的路径，则通过bfs去找箱子的最短路径
2.由于是人推箱子，所以在找箱子的路径是，需要通过bfs去判断人能否推箱子到那个路径上。
要点（嵌套bfs）
bfs_box时，需注意：是否在界内，是否不为墙，是否人能到推它的相应位置，判重（判断人是否已经在这里推过箱子了，防止TLE）
bfs_per时，需注意：是否在界内，是否不为墙，判重（人是否已经走过这）
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int room[][];//房间布置
int n,m,res;//行、列 ,res为最终结果
struct node
{
int x,y,step;//x,y为坐标，step指箱子走过的路
}per,fin,box;//分别指人，终点，以及箱子
bool pvis[][];//人能到的位置
bool pbvis[][][][];//判重
int rx[]={,,,-};
int ry[]={,-,,};
void bfs_per()//找出人当前可以走的位置
{
queue<node>qper;
memset(pvis,false,sizeof(pvis));
qper.push(per);
node cur,next;
while(!qper.empty())
{
cur=qper.front();
qper.pop();
pvis[cur.x][cur.y]=true;
for(int i=;i<;i++)
{
next.x=cur.x+rx[i];
next.y=cur.y+ry[i];
if(next.x>=&&next.x<n&&next.y>=&&next.y<m)//在界内
if(room[next.x][next.y]==)//可走
if(!pvis[next.x][next.y])
qper.push(next);
}
}
}
void bfs_box()//找出箱子可移动的最短路径
{
queue<node>qbox;
qbox.push(box);
qbox.push(per);
node cur,next;
while(!qbox.empty())
{
cur=qbox.front();//box所在位置
qbox.pop();
per=qbox.front();//人的位置
qbox.pop();
if(cur.x==fin.x&&cur.y==fin.y)
{
if(res==-||cur.step<res)
res=cur.step;
return ;
}
pbvis[cur.x][cur.y][per.x][per.y]=true;
room[cur.x][cur.y]=;//箱子人是不能走的
bfs_per();//人可以到达的位置
room[cur.x][cur.y]=;//回溯
for(int i=;i<;i++)
{
next.x=cur.x+rx[i];
next.y=cur.y+ry[i];
next.step=cur.step+;
if(next.x>=&&next.x<n&&next.y>=&&next.y<m) //在界内
if(room[next.x][next.y]==)//箱子位置可达
if(pvis[cur.x-rx[i]][cur.y-ry[i]])//人能到箱子的反方向
if(!pbvis[next.x][next.y][cur.x][cur.y])//判重防止TLE
{
qbox.push(next);//箱子当前的位置
qbox.push(cur);// 人当前的位置
}
}
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
cin>>room[i][j];
if(room[i][j]==)
box.x=i,box.y=j,box.step=;//初始化
else if(room[i][j]==)
fin.x=i,fin.y=j,room[i][j]=;//处理成可以走的地方
else if(room[i][j]==)
per.x=i,per.y=j,room[i][j]=;
}
res=-;
memset(pbvis,false,sizeof(pbvis));//都没有访问过
bfs_box();
printf("%d\n",res);
}
return ;
}