Zookeeper安装 ssh命令 java 线程池 ssl networking background 河南普通话 bootstrap侧边栏 hash怎么下载 js获取body的高度 css面试题 lora开发 office配置进度 vue与html5 python正则表达式例子 python中set的用法 python正则匹配数字 java基础编程 java线程中断 javasocket java日期转时间戳 php连接mssql 脚本之家 decimalformat 微信签名一句话至自己 相关软件 c语言程序100例 eclipse中文版下载 big5 mssql 电子商城系统 王者荣耀自动刷冒险 免费微信答题制作 arm体系结构与编程 苹果手机验机软件 国都证券官网下载 ps怎么画漫画 正则表达式替换 英特尔显卡驱动官方 nastran
当前位置: 首页 > 学习教程  > 编程语言

推箱子(字节2018校招Android)

2021/2/13 18:13:33 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

推箱子 题目链接 题目简介 有一个推箱子的游戏, 一开始的情况如下图: 上图中, ‘.’ 表示可到达的位置, ‘#’ 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向…

推箱子

题目链接

题目简介

有一个推箱子的游戏, 一开始的情况如下图:
在这里插入图片描述
上图中, ‘.’ 表示可到达的位置, ‘#’ 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;
…S0… -> …S0.
注意不能将箱子推动到’#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。

解题思路

我一开始看到这道题时感觉难度会比较大,没有什么思路,其实不要被题面吓到了。

  • 看到最少需要多少时就会想到用BFS(广度优先搜索)
  • 然后在搜索过程中记录每一步的当前你的位置和箱子的位置,只需要考虑两个情况
    • 你的下一步不是箱子所在的位置,此时只需要更新你的位置
    • 你的下一步是箱子所在的位置 ,这个时候如果可以推动箱子的话,需要更新你的位置和箱子的位置

代码

#include<bits/stdc++.h>
using namespace std;
int m,n,curx,cury,boxx,boxy,destx,desty;
int mov[4][2] = {1,0,-1,0,0,1,0,-1};
bool vis[50][50][50][50];
char graph[50][50];
struct state{
    int curx,cury,boxx,boxy,step;
    state(int a,int b,int c,int d,int e):curx(a),cury(b),boxx(c),boxy(d),step(e){}
};
int bfs(){
    queue<state>q;
    q.push(state(curx,cury,boxx,boxy,0));
    vis[curx][cury][boxx][boxy] = 1;
    while(!q.empty()){
        state cur = q.front();
        q.pop();
        if(cur.boxx==destx&&cur.boxy==desty)return cur.step;
        for(int i=0;i<4;i++){
            int new_curx = cur.curx + mov[i][0];
            int new_cury = cur.cury + mov[i][1];
            if(new_curx<0||new_curx>=n||new_cury<0||new_cury>=m||graph[new_curx][new_cury]=='#')continue;
			if(new_curx!=cur.boxx||new_cury!=cur.boxy){
				if(vis[new_curx][new_cury][cur.boxx][cur.boxy])continue;
                q.push(state(new_curx,new_cury,cur.boxx,cur.boxy,cur.step+1));
                vis[new_curx][new_cury][cur.boxx][cur.boxy] = 1;
            }else if(new_curx==cur.boxx&&new_cury==cur.boxy){
                int new_boxx = cur.boxx+mov[i][0];
                int new_boxy = cur.boxy+mov[i][1];
                if(new_boxx<0||new_boxx>=n||new_boxy<0||new_boxy>=m||graph[new_boxx][new_boxy]=='#')continue;
                if(vis[new_curx][new_cury][new_boxx][new_boxy])continue;
				q.push(state(new_curx,new_cury,new_boxx,new_boxy,cur.step+1));
				vis[new_curx][new_cury][new_boxx][new_boxy] = 1;
            }
        }
    }
    return -1;
}
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin >> graph[i][j];
            if(graph[i][j]=='S'){
                curx = i;cury = j;
            }else if(graph[i][j]=='0'){
                boxx = i;boxy = j; 
            }else if(graph[i][j]=='E'){
                destx = i;desty = j;
            }
        }
    cout << bfs() << "\n";
}

本文链接: http://www.dtmao.cc/news_show_700215.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?