题解 | #迷宫#

有限的超能力

1. 我发现牛客上有些题目就喜欢这种在基础考点之上再加上一点点。比如这个题目就是bfs之外，加上一条激光。
2. 思路解析：
   1. 先从end点出发，用bfs去遍历完所有可达空间，并记录可达空间的所有行和列，比如endI、endJ。
   2. 再从start出发，同样用bfs去遍历所有可达空间，如果这些可达空间属于endI和endJ，那么就是可以通的。
   3. 这里并没有真的模拟激光去打通一行或者一列。

具体代码如下：

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] firstLine = in.nextLine().split(" ");
        int m = Integer.parseInt(firstLine[0]);
        int n = Integer.parseInt(firstLine[1]);
        char[][] grid = new char[m][n];
        int[] start = new int[2];
        int[] end = new int[2];
        for (int i = 0; i < m; i++) {
            String line = in.nextLine();
            for (int j = 0; j < line.length(); j++) {
                char ch = grid[i][j] = line.charAt(j);
                if (ch == 'S') {
                    start = new int[] {i, j};
                } else if (ch == 'E') {
                    end = new int[] {i, j};
                }
            }
        }
        boolean[] endI = new boolean[m];
        boolean[] endJ = new boolean[n];
        Queue<int[]> q = new LinkedList<>();
        q.add(end);
        endI[end[0]] = true;
        endJ[end[1]] = true;
        int[][] directions = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Set<Integer> visited = new HashSet<>();
        visited.add(hashKey(n, end[0], end[1]));
        while (!q.isEmpty()) {
            int[] point = q.poll();
            for (int[] dir : directions) {
                int nextI = point[0] + dir[0];
                int nextJ = point[1] + dir[1];
                if (nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n ||
                        grid[nextI][nextJ] == '#') {
                    continue;
                }
                int key = hashKey(n, nextI, nextJ);
                if (!visited.contains(key)) {
                    q.offer(new int[] {nextI, nextJ});
                    endI[nextI] = true;
                    endJ[nextJ] = true;
                    visited.add(hashKey(n, nextI, nextJ));
                }
            }
        }
        boolean ok = endI[start[0]] || endJ[start[1]];
        if (ok) {
            System.out.println("YES");
            return;
        }
        q.offer(start);
        visited = new HashSet<>();
        visited.add(hashKey(n, start[0], start[1]));
        while (!q.isEmpty()) {
            int[] point = q.poll();
            // enqueue next point
            for (int[] dir : directions) {
                int nextI = point[0] + dir[0];
                int nextJ = point[1] + dir[1];
                if (nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n) {
                    continue;
                }
                // check
                if (endI[nextI] || endJ[nextJ]) {
                    ok = true;
                    break;
                }
                if (grid[nextI][nextJ] == '#') {
                    continue;
                }
                // 进队列
                int key = hashKey(n, nextI, nextJ);
                if (!visited.contains(key)) {
                    q.offer(new int[] {nextI, nextJ});
                    visited.add(hashKey(n, nextI, nextJ));
                }
            }
        }
        System.out.println(ok ? "YES" : "NO");

    }

    public static int hashKey(int n, int i, int j) {
        return i * n + j;
    }
}