推箱子
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5313 Accepted Submission(s): 1490
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
/*
HDU 1254 推箱子BFS广搜
两个位置：箱子的位置和人的位置,每次搜索箱子的位置，
判断人是否能到达箱子后面的那点！
*/
/*
HDOJ 1871 贪心排序
题意 几间宾馆，入住学生，每个组在一间，输入若干组的人数，能否住宿？
排序即可
*/
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
using namespace std;
int n,m;
struct node{
int x,y,step;
int map[10][10];
bool check()
{
if(x>=0&&x<n&&y>=0&&y<m)
return true;
return false;
}
};
node s,st,en,pe,ss,en2,st2;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int str[10][10];
bool pepCanReach(node n1)//搜索人是否能到达指定位置
{
queue<node>q;
ss=n1;
int flag[10][10];
memset(flag,0,sizeof(flag));
for(int i=0;i<n;i++)//找到人的起点
{
for(int j=0;j<m;j++)
if(n1.map[i][j]==4)
{
ss.x=i;
ss.y=j;
ss.step=0;
}
}
if(ss.x==pe.x&&ss.y==pe.y)
return true;
q.push(ss);
flag[ss.x][ss.y]=1;
while(!q.empty())//从人的起点开始搜索 是否到达pe
{
st2=q.front();
q.pop();
for(int i=0;i<4;i++)
{
en2=st2;
en2.step++;
en2.x+=dir[i][0];
en2.y+=dir[i][1];
//目标点不是墙也不是箱子
if(en2.check()&&!flag[en2.x][en2.y]&&(n1.map[en2.x][en2.y]!=1&&n1.map[en2.x][en2.y]!=2))
{
flag[en2.x][en2.y]=1;
if(en2.x==pe.x&&en2.y==pe.y)
return true;
q.push(en2);
}
}
}
return false;
}
int BFS()
{
queue<node> q;
q.push(s);
int vis[10][10][4],i;
memset(vis,0,sizeof(vis));
while(!q.empty()) //从箱子开始搜
{
st=q.front();
q.pop();
for(i=0;i<4;i++)//四个方向
{
en=st;
en.x+=dir[i][0];
en.y+=dir[i][1];
en.step++;
//判断 箱子的下一个位置是否合法 且没走过
if(en.check()&&str[en.x][en.y]!=1&&!vis[en.x][en.y][i])
{
pe.x=st.x-dir[i][0];//人要在的位置 与箱子下一个位置相对
pe.y=st.y-dir[i][1];
if(pe.check()==false)
continue;
if(pepCanReach(en))//寻找人的位置 判断人是否可以到达pe的地方
{
swap(en.map[en.x][en.y],en.map[st.x][st.y]);//把表格更新
swap(en.map[pe.x][pe.y],en.map[ss.x][ss.y]);//交换2个位置
vis[en.x][en.y][i]=1;
if(str[en.x][en.y]==3)//结束
return en.step;
q.push(en);
}
}
}
}
return -1;
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&str[i][j]);//图
s.map[i][j]=str[i][j];
if(str[i][j]==2)//箱子的位置 s保存箱子
{
s.x=i;
s.y=j;
s.step=0;
}
}
printf("%d\n",BFS());
}
return 0;
}