文档章节

题目:两道迷宫类型题

o
 osc_fmg49rzg
发布于 2019/03/20 15:54
字数 1478
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

 1.迷宫寻路

题目描述

假设一个探险家被困在了地底的迷宫之中,要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成,有的部分是墙,有的部分是路。迷宫之中有的路上还有门,每扇门都在迷宫的某个地方有与之匹配的钥匙,只有先拿到钥匙才能打开门。请设计一个算法,帮助探险家找到脱困的最短路径。如前所述,迷宫是通过一个二维矩阵表示的,每个元素的值的含义如下 0-墙,1-路,2-探险家的起始位置,3-迷宫的出口,大写字母-门,小写字母-对应大写字母所代表的门的钥匙

输入描述:

迷宫的地图,用二维矩阵表示。第一行是表示矩阵的行数和列数M和N
后面的M行是矩阵的数据,每一行对应与矩阵的一行(中间没有空格)。M和N都不超过100, 门不超过10扇。

输出描述:

路径的长度,是一个整数
示例1

输入


5 5
02111
01a0A
01003
01001
01111

输出


7



思路:用BFS, 创建类,成员中包含坐标,携带的钥匙,在这个坐标是第几步 三个信息。 其中钥匙的字母不超过26,INT的位数超过26,
   所以可以用一位int值的位运算保存持有的钥匙, 用三维数组,标识 此状态下(钥匙持有状态)是否走过此坐标。

需要注意的地方: Scanner 的 nextLine() 要提前多用一次吃点回车,或者用next()一个一个录入
         不要搞混 行于列 的关系 = =  


static int min=999999;
    static char[][] map=new char[110][110];
    static int next[][]={{1,0},{-1,0},{0,1},{0,-1}};
    static int m,n;
    static int [][][] visit = new int[110][110][1500];
public static void main(String[] args) { Scanner sc = new Scanner(System.in); m=sc.nextInt(); n=sc.nextInt(); sc.nextLine(); for(int i=0;i<m;i++) { map[i] = sc.nextLine().toCharArray(); } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(map[i][j]=='2'){ System.out.println(bfs(i,j));   return;
          } } } }
static int bfs(int x,int y){ /** * 首先拿到入口,压入queue * 开始判空que循环, * 用next数组,做循环判断四个方向,越界continue * 是出口,返回node.step +1 * 是小写,用(1<<char-'a')| node.k ,存储钥匙 * 是大写,判断有没有钥匙,没钥匙continue * 判断可走,在三维数组中写为1 * 并将新构建Node(携带最新的key,并step+1)压入queue */ LinkedList<Node> queue= new LinkedList<>(); queue.offer(new Node(x,y,0,0)); while(queue.size()>0){ Node t= queue.poll(); //System.out.println(" "+t.x+","+t.y+" ->"+t.k+" ===="+t.step); for(int k=0;k<4;k++){ int mx = t.x+next[k][0]; int my = t.y+next[k][1]; int key=t.k; if(mx<0||mx>=n||my<0||my>=m||map[mx][my]=='0') continue; if(map[mx][my]=='3')return t.step+1; if(map[mx][my]>='A'&&map[mx][my]<='Z'){ int o=map[mx][my]-'A'; if((key&(1<<o))==0)continue; } if(map[mx][my]>='a'&&map[mx][my]<='z'){ key=(1<<map[mx][my]-'a')|key; } if(visit[mx][my][key]==0) { visit[mx][my][key] = 1; queue.offer(new Node(mx,my,key,t.step+1)); } } } return -1; } public static class Node { int x, y, k, step; public Node(int x, int y, int k, int step) { this.x = x; this.y = y; this.k = k; this.step = step; } }

 

 

2.推箱子游戏

 

有一个推箱子的游戏, 一开始的情况如下图:
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 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

思路:BFS,与上题不同的是,上题需要记录的“状态”是钥匙的携带情况,此题的“状态”是“箱子的位置”,(即状态相同的情况下,
      走过的位置不饿能再走)
      每次判断移动后是否到了箱子的位置,如果是,则箱子也被推动,保存刷新的状态。
      如果不是,则进行普通的保存
      如果状态箱子的位置等于出口,则返回结果
import java.util.*;

public class Main {


    static char[][] map=new char[110][110];
    static int next[][]={{1,0},{-1,0},{0,1},{0,-1}};
    static int m,n;
    static int [][][][] visit = new int[60][60][60][60];
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n=sc.nextInt();
        m=sc.nextInt();
        sc.nextLine();
        for(int i=0;i<n;i++) {
            map[i] = sc.nextLine().toCharArray();
        }
        int r1=0,r2=0,b1=0,b2=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j]=='S') {
                    r1 = i;
                    r2 = j;
                }
                if(map[i][j]=='0'){
                    b1=i;
                    b2=j;
                }
            }
        }
        System.out.println(bfs(r1,r2,b1,b2));
    }
    static int bfs(int r1,int r2,int b1,int b2){
        LinkedList<Node> queue=new LinkedList<>();
        queue.offer(new Node(r1,r2,b1,b2));
        visit[r1][r2][b1][b2]=1;
        while(queue.size()>0){
            Node t= queue.poll();

            if(map[t.bx][t.by]=='E'){

                return visit[t.x][t.y][t.bx][t.by]-1;
            }
            for(int k=0;k<4;k++){
                int mx=t.x+next[k][0];
                int my=t.y+next[k][1];

                //System.out.println(mx+" ---- "+my);
                if(mx<0||mx>=n||my<0||my>=m||map[mx][my]=='#')continue;

                if(mx==t.bx&&my==t.by){
                    int mbx=t.bx+next[k][0];
                    int mby=t.by+next[k][1];
                    if(mbx>=n||mbx<0||mby<0||mby>=m
                            ||map[mbx][mby]=='#'||visit[mx][my][mbx][mby]!=0)continue;
                    visit[mx][my][mbx][mby]= visit[t.x][t.y][t.bx][t.by]+1;
                    queue.offer(new Node(mx,my,mbx,mby));
                }else{
                    if(visit[mx][my][t.bx][t.by]!=0)continue;
                    visit[mx][my][t.bx][t.by] = visit[t.x][t.y][t.bx][t.by]+1;
                    queue.offer(new Node(mx,my,t.bx,t.by));
                }
            }
        }
        return -1;
    }

    public static class Node {
        int x, y, bx, by;

        public Node(int x, int y, int bx, int by) {
            this.x = x;
            this.y = y;
            this.bx = bx;
            this.by = by;
        }
    }
}

 





o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
深搜(DFS)模板

当N较小时考虑搜索。 DFS大致模板 //会有相对应的方向变量 例如: dx[4].dy[4];void DFS(int x,int y){ { } int main(){ } 例题: P1605 迷宫: 1 #include <iostream> 2 #include......

osc_ny7uj9zu
2019/11/16
2
0
LeetCode 63、64 动态规划两题连刷,移动坐标的小技巧

本文分享自微信公众号 - TechFlow(techflow2019)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

承志Y
05/16
0
0
LeetCode 79,明明是走迷宫问题,为什么不能用宽搜呢?

点击上方蓝字,和我一起学技术。 本文分享自微信公众号 - TechFlow(techflow2019)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起...

承志Y
06/20
0
0
动态规划两题连刷,移动下标的小技巧

本文始发于个人公众号:TechFlow,原创不易,求个关注 今天是LeetCode的37篇,我们继续愉快的刷题。今天要刷的题目输出LeetCode 63和64两题,分别是Unique Paths II和Minimum Path Sum。 从题...

TechFlow2019
05/19
0
0
LeetCode 79,这道走迷宫问题为什么不能用宽搜呢?

本文始发于个人公众号:TechFlow,原创不易,求个关注 今天是LeetCode专题第48篇文章,我们一起来看看LeetCode当中的第79题,搜索单词(Word Search)。 这一题官方给的难度是Medium,通过率是...

TechFlow2019
06/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 01:15 US Supreme Court deems half of Oklahoma a Native American Reservation - (reuters.com) 美国最高法院认为俄克拉荷马州的一半是印第安人保留地 得分:131 | 评...

FalconChen
50分钟前
16
0
OSChina 周五乱弹 —— 求求你吃了我吧,不要再玩弄食物的感情了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @巴拉迪维 :张喆的单曲《陷阱 》 这首歌已经在网易找不到原唱了,不知道被哪家买了版权。#今日歌曲推荐# 《陷阱 》- 张喆 手机党少年们想听歌...

小小编辑
今天
24
1
清华陈文光教授:AI 超算基准测试的最新探索和实践。

道翰天琼认知智能平台为您揭秘新一代人工智能。 无规矩不成方圆。放在超级计算机的研发领域,没有一个大家普遍接受的算力评测指标,便难以推动超算迅猛发展。 而现在伴随着人工智能的发展,大...

jackli2020
今天
7
0
@RequestMapping, consumes 提交简单有意思的测试

getParm @GetMapping("getParm")public Result getParm(String id){ System.out.println(); return ResultFactory.success(id);} 等同于 == bodyParm @PostMapping("bodyParm......

莫库什勒
今天
25
0
63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
今天
55
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部