蓝桥杯2019年第十届JavaB组真题题目+解析+代码+答案:5.迷宫

本文涉及的产品
云解析DNS,个人版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 蓝桥杯2019年第十届JavaB组真题题目+解析+代码+答案:5.迷宫

题目描述:

下图给出了一个迷宫的平面图,其中标记为1的是障碍,0的是可以通行的地方

010000

000100

001001

110000

迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫,从入口开始,可以按DRRURRDDDR 的顺序通过迷宫, 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫(30 行 50 列),请找出一种通过迷宫的方式, 其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。

解题思路:

> 本题是典型的迷宫问题,可以利用bfs(广度优先遍历)
> 也可以用dfs进行搜索路径,但最终要字典序最小,所以dfs不太容易操作
> 广搜的顺义要以D-L-R-U进行,因为要字典序最小
> 这点可以利用4次循环即可
> 怎么判断是最小路径呢?
> 因为是广搜,要一层一层的搜
> 所以当前节点探寻了每个和它相邻的节点
> 一但到达终点即退出,最小路径为探索的层数,这点和深搜不太相同,
> dfs是不断进行递归回溯,进行比较找最小值
> 而bfs可以利用自身优势确定最小值

代码:

public class Main {
  public static int dir[][] = new int[][] {{1,0},{0,-1},{0,1},{-1,0}};
  public static char direction[] = new char[] {'D','L','R','U'};
  public static int[][] map=new int[30][50];
  public static boolean[][] visit=new boolean[30][50];
    public static void main(String[] args){
      Scanner sc=new Scanner(System.in);
      for(int i=0;i<30;i++) {
        String s=sc.next();
        for(int j=0;j<50;j++) {
          map[i][j]=s.charAt(j)-'0';
        }
      }
      bfs(new Point(0, 0));
  }
    public static void bfs(Point start) {
      Queue<Point> q=new LinkedList<Point>();
      q.add(start);
      visit[start.i][start.j]=true;
      while(!q.isEmpty()) {
        Point p=q.peek();
        if(p.i==29&&p.j==49) {
          System.out.println(p.step);
          System.out.println(p.way);
          return;
        }
        for(int i=0;i<4;i++) {
          int new_i=p.i+dir[i][0];
          int new_j=p.j+dir[i][1];
          Point temp=new Point(new_i,new_j);
          if(new_i>=0&&new_j>=0&&new_i<30&&new_j<50&&!visit[new_i][new_j]&&map[new_i][new_j]!=1) {
            visit[new_i][new_j]=true;
            temp.step=p.step+1;
            temp.way=p.way+direction[i];
            q.add(temp);
          }
        }
        q.poll();
      }
    }
}
class Point{
  int i;
  int j;
  int step;
  String way;
  public Point() {
    i=j=step=0;
    way="";
  }
  public Point(int i,int j) {
    this.i=i;
    this.j=j;
    step=0;
    way="";
  }
}

答案:

(最少一共186步)
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR


目录
相关文章
|
20天前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
24天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
17 1
|
24天前
|
存储
初阶编程题积累(3)——最接近的三数之和(题目描述、示例、题目思路、题解、解析)
初阶编程题积累(3)——最接近的三数之和(题目描述、示例、题目思路、题解、解析)
13 0
|
2月前
|
网络安全 数据安全/隐私保护 计算机视觉
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
|
25天前
|
Java
P9242 [蓝桥杯 2023 省 B] 接龙数列JAVA,边权为1的最短路问题,洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列​编辑力扣1926.迷宫离入口最近的出口力扣433.
P9242 [蓝桥杯 2023 省 B] 接龙数列JAVA,边权为1的最短路问题,洛谷P9242 [蓝桥杯 2023 省 B] 接龙数列​编辑力扣1926.迷宫离入口最近的出口力扣433.
|
2月前
蓝桥杯真题代码记录(直线
蓝桥杯真题代码记录(直线
16 0
|
2月前
蓝桥杯真题代码记录(卡片
蓝桥杯真题代码记录(卡片
20 0
|
2月前
蓝桥杯真题代码记录(最优清零方案
蓝桥杯真题代码记录(最优清零方案
14 0
|
2月前
蓝桥杯真题代码记录(蜂巢
蓝桥杯真题代码记录(蜂巢
14 0
|
2月前
蓝桥杯真题代码记录(数位排序
蓝桥杯真题代码记录(数位排序
17 0

推荐镜像

更多