字节跳动 编程题1 推箱子 bfs

题目描述

有一个推箱子的游戏, 一开始的情况如下图:

img

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 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;
}
Last modification:December 7th, 2020 at 09:13 pm
如果觉得我的文章对你有用,请随意赞赏