题解 | 迷宫寻路

import java.util.Scanner;

import java.util.Queue;
import java.util.LinkedList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] arr = in.nextLine().split(" ");
        int m = Integer.valueOf(arr[0]);
        int n = Integer.valueOf(arr[1]);
        char[][] grid = new char[m][n];
        
        int startX = 0;
        int startY = 0;
        for (int i = 0; i < m; i++) {
            String str = in.nextLine();
            for (int j = 0; j < n; j++) {
                grid[i][j] = str.charAt(j);
                if (grid[i][j] == '2') {
                    startX = i;
                    startY = j;
                }
            }
        }
        
        int result = bfs(startX, startY, grid);
        System.out.println(result);
    }

    private static int bfs(int startX, int startY, char[][] grid) {

        // 记录x,y,key,step
        Queue<int[]> queue = new LinkedList<>();
        // 记录访问状态
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][][] visited = new boolean[m][n][1024];
        visited[startX][startY][0] = true;
        // 方向数组
        int[][] direction = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

        queue.offer(new int[]{startX, startY, 0, 0});
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            if (grid[arr[0]][arr[1]] == '3') {
                // 返回结果步数
                return arr[3];
            }
            for (int i = 0; i < 4; i++) {
                int nextX = arr[0] + direction[i][0];
                int nextY = arr[1] + direction[i][1];
                if (nextX >= m || nextX < 0 || nextY >= n || nextY < 0 || grid[nextX][nextY] == '0') {
                    continue;
                }
                int key = arr[2];
                if (grid[nextX][nextY] >= 'a' && grid[nextX][nextY] <= 'z') {
                    key = key | (1 << (grid[nextX][nextY] - 'a'));
                }
                if (grid[nextX][nextY] >= 'A' && grid[nextX][nextY] <= 'Z' && (key & (1 << grid[nextX][nextY] - 'A')) == 0) {
                    continue;
                }
                if (!visited[nextX][nextY][key]) {
                    visited[nextX][nextY][key] = true;
                    queue.offer(new int[]{nextX, nextY, key, arr[3] + 1});
                }
            }
        }
        return 0;
    }
}