蓝桥杯第十届 JAVAB组 E迷宫-白红宇

蓝桥杯第十届 JAVAB组 E迷宫

阅读量：6201 次

发布时间：2019-06-21

本文共 3093 字，大约阅读时间需要 10 分钟。

/*试题 E: 迷宫    本题总分：15 分【问题描述】下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。010000000100001001110000迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D

解题思路：

1、广度优先搜索：遍历从起点到终点每一个点到重点的最短距离逆向搜索

2、深度优先搜索：根据广度优先搜索的预处理，深度搜索一条最短的路径

答案正确

import java.util.*;public class E5{    static int n,m;    static char[][] maze;    static int[][] dis;    static int[][] dir = {
   {1 ,0},{0,-1 },{0,1 },{-1 ,0}};    static char[] c = {'D','L','R','U'};        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        Queue
     
       queue = new LinkedList
      
       ();        dis = new int[30][50];        maze = new char[30][50];                n = scanner.nextInt();        m = scanner.nextInt();                for(int i=0;i
       
        =n||yy<0|yy>=m||maze[xx][yy]=='1'||dis[xx][yy]!=0) continue;   //注意这里dis[n-1 ][m-1 ]=0,但是已经遍历过了                System.out.println(xx+" "+yy);                queue.add(xx*m+yy);                dis[xx][yy] = dis[temp/m][temp%m] + 1 ;                if(xx==0&&yy==0) break;            }        }        dis[n-1 ][m-1 ] = 0;  //由于遍历不止一遍，所以值不是0，要在定义一遍            String record="";        int x = 0,y = 0;                        while(x!=n-1 ||y!=m-1 ) {            for(int i=0;i<4;i++) {                int xx = x + dir[i][0];                int yy = y + dir[i][1 ];                if(xx<0||xx>=n||yy<0|yy>=m||maze[xx][yy]=='1') continue;                if(dis[x][y]==dis[xx][yy]+1 ) {                    x = xx; y = yy;                    record += c[i];                    break;                }            }        }        System.out.println(record.length());        System.out.println(record);    }} //DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUUL //ULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

最短路径-->BFS

记录路径--> 结构体中String存储路径

答案错误

import java.util.*;public class Main{    static class node{        int x;        int y;        String path;        public node(int x,int y,String path) {            this.x = x;            this.y = y;            this.path = path;        }    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);                Queue
     
       queue = new LinkedList
      
       ();        int[][] dir = {
   {0 ,1 },{0 ,-1 },{-1 ,0 },{1 ,0 }};        char[] c = {'R','L','U','D'};        int[][] maze = new int[30 ][50 ];                int n = scanner.nextInt();        int m = scanner.nextInt();        for(int i=0 ;i
       
        =n||yy<0 ||yy>=m||maze[xx][yy]==1 ) continue;                maze[xx][yy] = 1 ;                queue.add(new node(xx, yy, temp.path+c[i]));                if(xx==n-1 &&yy==m-1 )                      System.out.println(temp.path+c[i]);            }        }           }}