题解 1923: 蓝桥杯算法提高VIP-学霸的迷宫(BFS JAVA简洁代码)

解题思路:
非常简单经典的bfs题目，唯一不同的是需要交换子节点的访问顺序，来保证同一长度下字典序最小的输出。以下对代码做简单说明

1.代码中先将01倒置，因为int类型的默认值为0，这样就不需要手动生成数组边界

2.地图大小为(n+2) * (m+2)，对长宽分别做了padding=1，在循环中就不需判断溢出情况。

3.对于访问过的节点，将map[i][j]置为0，以不能访问代表已经访问过。
注意事项:

无

参考代码:

import java.util.*;
import java.io.*;

// https://www.dotcpp.com/oj/problem1923.html
// bfs
// 多条最短路径下选择字典序最小的一条, 因此需要交换访问顺序


public class Main {
    static class Loc{
        int x, y;
        int count;  // 计数
        String path; // 方向
        Loc(int x, int y, String path, int count){
            this.x = x;
            this.y = y;
            this.path = path;
            this.count = count;
        }
    }
    static StreamTokenizer cin;
    static PrintWriter out;
    static int n;  // 行
    static int m;  // 列
    static int[][] map;
    static int k = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        n = nextInt();
        m = nextInt();
        cin.ordinaryChars(0, 255);
        cin.nextToken();
        map = new int[n+2][m+2];
        // 初始化边界为不可进入
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < m+1; j++)
                map[i][j] = (nextNum()+1)%2;
            cin.nextToken();
        }
        Queue<Loc> que = new LinkedList<>();
        map[1][1] = 0;
        Loc t = new Loc(1, 1, "", 0);
        que.add(t);
        while(!que.isEmpty()){
            t = que.poll();
            if(t.x==n && t.y==m)
                break;
            map[t.x][t.y] = 0;  // 不重复走路
            if(map[t.x+1][t.y] == 1){// 可以向下走
                que.add(new Loc(t.x+1, t.y, t.path+"D", t.count+1));
                map[t.x+1][t.y] = 0;
            }

            if(map[t.x][t.y-1] == 1){  // 可以向左走
                que.add(new Loc(t.x, t.y-1,t.path+"L", t.count+1));
                map[t.x][t.y-1] = 0;
            }
            if(map[t.x][t.y+1] == 1){// 可以向右走
                que.add(new Loc(t.x, t.y+1, t.path+"R", t.count+1));
                map[t.x][t.y+1] = 0;
            }

            if(map[t.x-1][t.y] == 1) {// 可以向上走
                que.add(new Loc(t.x-1, t.y, t.path+"U", t.count+1));
                map[t.x-1][t.y] = 0;
            }

        }
        out.println(t.count);
        out.println(t.path);
        out.flush();
        out.close();
    }

    static int nextInt() throws IOException{
        cin.nextToken();
        return (int)cin.nval;
    }

    static int nextNum() throws IOException{
        cin.nextToken();
        return cin.ttype-48;
    }
}