蓝桥杯2022年第十三届省赛真题-回忆迷宫 （暴力加深搜）

标签：真题 int 迷宫 蓝桥 static 2022 移动 initY initX

题目描述

爱丽丝刚从一处地下迷宫中探险归来，你能根据她对于自己行动路径的回忆，帮她画出迷宫地图吗？ 

迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的移动步骤，每个移动步骤可能是上下左右四个方向中的一种，表示爱丽丝往这个方向走了一格。你需要根据这些移动步骤给出一个迷宫地图，并满足以下条件： 

1、爱丽丝能在迷宫内的某个空地开始，顺利的走完她回忆的所有移动步骤。 

2、迷宫内不存在爱丽丝没有走过的空地。 

3、迷宫是封闭的，即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处视为迷宫外，所有不与迷宫外联通的空地都视为是迷宫内。（迷宫地图为四联通，即只有上下左右视为联通） 

4、在满足前面三点的前提下，迷宫的墙的数量要尽可能少。 

输入格式

第一行一个正整数 N，表示爱丽丝回忆的步骤数量。

接下来一行 N 个英文字符，仅包含 UDLR 四种字符，分别表示上（Up）、下（Down）、左（Left）、右（Right）。 

样例输入

17
UUUULLLLDDDDRRRRU

样例输出

 ***** 
*     *
* *** *
* *** *
* *** *
*     *
 ***** 

1. 输入

static int n; // 使用static是为了全局访问，避免传参
static String str;

n = sc.nextInt();
str = sc.next();

2. 我们需要得知开始移动时的坐标

如果你可以向上移动0格，那上面会是墙

那就是初始坐标x=2，

那如果可以移动1格，第一排是墙，第二排是可移动的空位，第三排是你目前的位置

所以initX等于=x+2;

initY同理

public static void initMap(){ // 获取初始位置
    int x = 0, y = 0;
    initX = Math.max(initX, x+2);
    initY = Math.max(initY, y+2);
    for (int i = 1; i <= n; i++) {
        switch (str.charAt(i-1)){
            case 'U':
                x++;
                initX = Math.max(initX, x+2);
                break;
            case 'D':
                x--;
                break;
            case 'L':
                y++;
                initY = Math.max(initY, y+2);
                break;
            case 'R':
                y--;
                break;
        }
    }
}

3.接下来就可以从点initX, initY开始根据指令移动，移动到的位置就是空位，在这之前，我们声明一个二维数组表示这个迷宫

因为不知道具体大小，只能按最坏的情况打算，n的值小于100，就算全是一个方向105*105大小就可以了，而且不算特别占空间，毕竟是O（1），在

对于map[i][j], 0是初始化时的，也代表未确认的格子，1代表可通行的格子，2代表墙，3代表墙外空格

static int[][] map = new int[105][105]; 

然后就根据指令移动，把路过的格子设置为1

　　public static void dfsCross(int x, int y){  // initX和initY传参为x和y
        for(int i=1;i<=n;i++){
            map[x][y] = 1;　　　　　　      // 每次路过的格子置为1
            row = Math.max(row, x);　　　　// 根据当前的位置算出地图最大行和列
            col = Math.max(col, y);
            switch (str.charAt(i-1)){
                case 'U':
                    x--;
                    break;
                case 'D':
                    x++;
                    break;
                case 'L':
                    y--;
                    break;
                case 'R':
                    y++;
                    break;
            }
        }
        map[x][y] = 1;
        row = Math.max(row, x)+1;  　　　　// 最后一行和一列必定是墙，所以加一
        col = Math.max(col, y)+1; 
    }

4.接下来把所有旁边是空地而自身没有被搜索到的格子设置为2，因为指令保证了所有除墙外空格的空格都会经过，所以也不能直接把其他格子置为墙
需要后面找出没有被标记到的格子，并设置为3

　　　　　for(int i=1;i<=row;i++){  // 
            for(int j=1;j<=col;j++){
                if(map[i][j]==0){
                    if(map[i-1][j]==1||map[i+1][j]==1||map[i][j-1]==1||map[i][j+1]==1){ // 这里判断旁边为空格的格子置为墙
                        map[i][j]=2; 
                    }
                }
            }
        }

5.搜索把剩下没有搜索到的各自置为墙外空格

这里是dfs搜索墙外空格的方法

　　 static int[][] move={{-1,0},{1,0},{0,-1},{0,1}}; // 直接用循环替换方向，不需要自己手动写四个方向的判断

　　 public static void dfs(int x, int y){
        int nextX, nextY;
        for (int i = 0; i < 4; i++) {
            nextX = x + move[i][0]; 
            nextY = y + move[i][1];
            if(nextX>0&&nextY>0&&nextX<=row&&nextY<=col&&map[nextX][nextY]==0){ // 先判断下一个位置是否存在，在判断是否之前的搜索中没有搜索到，直接置为3
                map[nextX][nextY]=3;
                dfs(nextX,nextY);   
            }
        }
    }

　实用dfs方法快速把剩下的格子置为3

　　　　 for(int i=1;i<=row;i++) {
            if(i==1||i==row){
                for(int j=1;j<=col;j++){
                    if(map[i][j]==0){
                        map[i][j]=3;
                        dfs(i,j);
                    }
                }
            }else{
                if(map[i][1] == 0){
                    map[i][1] = 3;
                    dfs(i,1);
                }
                if(map[i][col] == 0){
                    map[i][col] = 3;
                    dfs(i, col);
                }
            }
        }

6.遍历map，map[i][j]等于1或3打印空格，否则打印*

　　　　　for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(map[i][j]==1||map[i][j]==3){
                    System.out.print(" ");
                }else{
                    System.out.print("*");
                }
            }
            System.out.println();
        }

 

 

 

标签：真题,int,迷宫,蓝桥,static,2022,移动,initY,initX
From： https://www.cnblogs.com/zhexian233/p/17149804.html