字节跳动 编程题1 推箱子 bfs
题目描述
有一个推箱子的游戏, 一开始的情况如下图:
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
输入描述:
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);后面为n行字符串,每行字符串有m字符, 表示游戏盘面;
输出描述:
一个数字,表示最少几步能完成游戏,如果不能,输出-1;
示例1
输入
3 6
.S#..E
.#.0..
......
输出
11
解题思路
这是一个标准的推箱子游戏,应该大家都玩过。相当于用广搜实现的推箱子游戏,棋盘不能越界,所以可以假设棋盘外面也是一圈围墙。起点和终点虽然用SE表示,本质上也是点‘.’。如果箱子进入死角,则一定推不出来,所以扫描一遍棋盘,将所有的死角标记X记号,judge函数实现的。棋盘中,所有的情况用人物位置和箱子位置表示,既用vis数组表示,初始化为0,走过就标记为1,避免重复。广搜的时候,人朝4个方向走就行,如果走到箱子的位置,则把箱子朝同样的方向推一步,用vis记录状态,避免进入死循环。
代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1e3+5; //
char arr[maxn][maxn]; //游戏棋盘
int n,m;
int sx,sy; //人物起始位置
int bx,by; //箱子起始位置
int ex,ey;
struct node{
int x,y; //当前点坐标
int h,d; //当前箱子坐标
int step;
};
const int maxn_ = 55;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int vis[maxn_][maxn_][maxn_][maxn_]; //1 表示已经走过了
int bfs(int sx,int sy)
{
queue<node> q;
node f; //f表示队首
f.x=sx;
f.y=sy;
f.h=bx;
f.d=by;
f.step=0;
vis[sx][sy][bx][by]=1; //一开始的状态标记为1
q.push(f); //将初始状态入队
int t=1e6+5;
while(!q.empty()) //当队不空时
{
t--;
if(t==0)
{
return -1;
}
f=q.front(); //f接收队首
//cout<<f.x<<" "<<f.y<<endl;
if(f.h==ex && f.d==ey) //如果队首坐标为E点坐标,则返回答案
{
return f.step;
}
q.pop(); //出队操作
int nstep=f.step+1; //下一步的步数为0
int nbx=f.h; //表示盒子的横坐标下一步的盒子假设还没移动
int nby=f.d;
for(int i=0;i<4;++i)
{
int nx=f.x+dir[i][0]; //四个方向的某一个方向坐标
int ny=f.y+dir[i][1];
if(nx<0 || nx>=n || ny<0 || ny>=m || arr[nx][ny]=='#') //坐标不合法
{
continue; //如果出界或者遇到墙,则坐标不合法
}
if(f.h==ex && f.d==ey)
{
node temp ;
temp.x=nx;
temp.y=ny;
temp.step=f.step+1;
q.push(temp);
}
/*
if(vis[nx][ny][f.h][f.d]) //状态已经存在了
{
continue;
}*/
//if(arr[nx][ny]=='0')
//如果人物走的位置和箱子重复了,则箱子应该相应的方向推一步,并且记录更改当下状态vis
if(nx==f.h && ny==f.d)
{
int ox,oy;
ox=nx+dir[i][0];
oy=ny+dir[i][1];
if(ox<0 || ox>=n || oy<0 || oy>=m || arr[ox][oy]=='#' || arr[ox][oy]=='X') //坐标不合法
{
continue;
}
node temp;
temp.x=nx;
temp.y=ny;
temp.h=ox;
temp.d=oy;
temp.step=nstep;
if(!vis[temp.x][temp.y][temp.h][temp.d])
{
q.push(temp);
}
vis[temp.x][temp.y][temp.h][temp.d]=1;
}
else if(arr[nx][ny]=='.' || arr[nx][ny]=='X' || arr[nx][ny]=='E') //如过遇到的是.和X
{
node temp;
temp.x=nx;
temp.y=ny;
temp.h=nbx;
temp.d=nby;
temp.step=nstep;
if(!vis[nx][ny][nbx][nby]) //如果状态没遇到过,则入队
{
q.push(temp);
}
vis[temp.x][temp.y][temp.h][temp.d]=1; //这个状态标记为1
}
}
}
return -1;
}
void judge(int i,int j) //ij代表当前箱子坐标,判断箱子进入这里是否卡入了死角
{
//如果当前坐标超过上边界即i<1,则flag1置为1,或者如果上边有围墙#,则flag也置位1
int flag1=0,flag2=0,flag3=0,flag4=0;
if(i-1<0)
{
flag1=1;
}else if(arr[i-1][j]=='#')
{
flag1=1;
}
if(j-1<0)
{
flag2=1;
}else if(arr[i][j-1]=='#')
{
flag2=1;
}
if(i+1==n)
{
flag3=1;
}else if(arr[i+1][j]=='#')
{
flag3=1;
}
if(j+1==m)
{
flag4=1;
}else if(arr[i][j+1]=='#')
{
flag4=1;
}
if((flag1 && flag2) || (flag2 && flag3) || (flag3 && flag4) || (flag4 && flag1))
{
arr[i][j]='X';
}
}
int main()
{
memset(vis,0,sizeof(vis));
while(cin>>n>>m)
{
for(int i=0;i<n;++i)
{
scanf("%s",arr+i);
}
// 找到S、E、0的位置
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(arr[i][j]=='S')
{
sx=i;
sy=j;
}
if(arr[i][j]=='0')
{
bx=i;
by=j;
arr[i][j]='.';
}
if(arr[i][j]=='E')
{
ex=i;
ey=j;
}
}
}
// 扫描一遍棋盘,把所有箱子进入死角就出不来的地方打X标记
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(arr[i][j]=='#' || arr[i][j]=='E') continue;
judge(i,j);
}
}
//test map
/*
cout<<endl;
for(int i=0;i<n;++i)
{
cout<<arr[i]<<endl;
}*/
//
//然后广搜
cout<<bfs(sx,sy)<<endl;
}
return 0;
}
One comment
写的挺棒的!!!