标签搜索

目 录CONTENT

文章目录

字节--推箱子.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 4 阅读 / 4,057 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--推箱子

@[toc]

一、题目描述

有一个推箱子的游戏, 一开始的情况如下图:
在这里插入图片描述
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;
..S0.. -> ...S0.

注意不能将箱子推动到'#'上, 也不能将箱子推出边界;

现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。

  •  输入描述:
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;
  •  输出描述:
一个数字,表示最少几步能完成游戏,如果不能,输出-1;

输入例子1:
3 6
.S#..E
.#.0..
......

输出例子1:
11

二、分析

  •  在开始做题前,如果你看到树、图的最短路径你想到了什么?广搜,对,这道题就是
  •  将人所在位置与箱子所在位置以及所走步数看作整体,新建节点Node。
  •  首先初始位置入队,通过移动不断将还没有经过的下一位置节点入队,直至找到箱子之前箱子的位置是不变的
  •  当人找到箱子之后(即在箱子的一侧,上下左右),开始推箱子往另一侧走(下上右左),此时人和箱子的位置都开始移动,直至走到终点或无路可走结束。
  •  解决这道题分为两步
  •  ① 人在找到箱子之前单独移动,箱子原地不动;在这个过程中,人要从“S”走到箱子“0”的旁边(上下左右)。
  •  ② 人找到箱子之后和箱子一起向“另一侧”移动,..S0.. -> ...S0. 。

三、代码

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
//用来标记是否已经访问过
bool vis[N][N][N][N]; // vis[a][b][c][d] 表示人在 (a,b)处,

//游戏的初始数据
char maze[N][N];

//棋盘的行、列
//人的起始行、列
//箱子的起始行、列
//目标位置的行、列
int n,m,px,py,boxx,boxy,ex,ey;

//把任务的坐标、箱子的坐标、当前移动的次数封装在一起
struct Node
{
    int px,py,boxx,boxy,step;
    // 重载, step大的Node优先级小,在构建优先级队列时使用
    bool operator < (const Node& rs) const
    { 
        return rs.step < step;
    }
}s;

//控制4个方向
int dir[][2] = {1,0,-1,0,0,1,0,-1};

//判断是否满足条件
bool judge(int x,int y)
{
    if(x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == '#') 
    	return false;
    return true;
}

//广搜
int bfs()
{
	//初始节点
    s = {px,py,boxx,boxy,0};

	//优先级队列
    priority_queue<Node> q;
    q.push(s);
    //进行标记
    vis[px][py][boxx][boxy] = 1;
    while(!q.empty())
    {
        Node u = q.top();
        q.pop();
        
        //如果箱子到达目标地点,返回移动的次数
        if(u.boxx ==ex && u.boxy == ey) 
        	return u.step;
        	
        //枚举上下左右4个方向
        for(int i=0;i<4;i++)
        {
            int pxx = u.px + dir[i][0];
            int pyy = u.py + dir[i][1]; // 人往该方向走了一步
	
			//判断任务是否移动到箱子的周围
            int boxx = u.boxx,boxy = u.boxy;
            if(pxx == boxx && pyy == boxy) 
            { 
            	// 碰到了箱子则将箱子向外推动一格
                boxx += dir[i][0];
                boxy += dir[i][1];
            }
			
			//判断任务位置和箱子的位置是否满足条件
            if(!judge(pxx,pyy) || !judge(boxx,boxy)) 
            	continue;

			//判断是否已经访问过
            if(vis[pxx][pyy][boxx][boxy]) 
            	continue;
            vis[pxx][pyy][boxx][boxy] = 1;
            q.push({pxx,pyy,boxx,boxy,u.step + 1});
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d",&n,&m);
    
    for(int i = 0;i < n;i++)
    {
        scanf("%s",maze[i]);
        for(int j = 0;j < m;j++)
        {
        	//记录相关坐标信息
            if(maze[i][j] == '0')
             	boxx = i,boxy = j,maze[i][j]='.';
            if(maze[i][j]=='S') 
            	px = i,py = j,maze[i][j]='.';
            if(maze[i][j]=='E') 
            	ex = i,ey = j,maze[i][j]='.';
        }
    }
    printf("%d\n",bfs());
    return 0;
}
  •  另外一种写法:
#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);              //将初始状态入队

    while(!q.empty())       //当队不空时
    {
        f = q.front();        //f接收队首

        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(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;
}

int main()
{
    memset(vis,0,sizeof(vis));
    while(cin>>n>>m)
    {
        for(int i = 0;i < n;++i)
        {
            scanf("%s",arr + i);
        }
        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; 
                }     
            }
        }
        
        cout<<bfs(sx,sy)<<endl;
    }
    return 0;
}
0

评论区