题解 | 迷宫

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int n, m;
    static char[][] grid;
    static int[] sPos = new int[2];
    static int[] ePos = new int[2];
    static int[][] distS, distE;
    static int[] di = {0, 0, -1, 1};
    static int[] dj = {-1, 1, 0, 0};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            n = in.nextInt();
            m = in.nextInt();
            grid = new char[n][m];
            for (int i = 0; i < n; i++) {
                String line = in.next();
                for (int j = 0; j < m; j++) {
                    grid[i][j] = line.charAt(j);
                    if (grid[i][j] == 'S') {
                        sPos[0] = i;
                        sPos[1] = j;
                    }
                    if (grid[i][j] == 'E') {
                        ePos[0] = i;
                        ePos[1] = j;
                    }
                }
            }
            distS = bfs(sPos);
            distE = bfs(ePos);

            int[][] distTmpE = distE;
            //扩大一下distE的邻居
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(distE[i][j]!=-1&&grid[i][j]!='#'){
                        for(int k=0;k<4;k++){
                            int ni = i+di[k];
                            int nj = j+dj[k];
                            if(ni >= 0 && ni < n && nj >= 0 && nj < m)
                            distTmpE[ni][nj] = 0;
                        }
                    }
                }
            }
            if (distE[sPos[0]][sPos[1]] != -1) {
                System.out.println("YES");
                return;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (distS[i][j] == -1)continue;
                    for (int k = 0; k < 4; k++) {
                        int ni = i + di[k];
                        int nj = j + dj[k];
                        while (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                            if (distTmpE[ni][nj]!=-1) {
                                System.out.println("YES");
                                return;
                            }
                            ni += di[k];
                            nj += dj[k];
                        }

                    }
                }
            }
            System.out.println("NO");
        }
    }

    static int[][] bfs(int[] arr) {
        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], -1);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(arr);
        dist[arr[0]][arr[1]] = 0;
        while (!queue.isEmpty()) {
            int[] cut = queue.poll();
            int i = cut[0];
            int j = cut[1];

            for (int k = 0; k < 4; k++) {
                int ni = i + di[k];
                int nj = j + dj[k];

                if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == '.' &&
                        dist[ni][nj] == -1) {
                    dist[ni][nj] = dist[i][j] + 1;
                    queue.offer(new int[] {ni, nj});
                }
            }

        }
        return dist;
    }
}