Leetcode 1926. Nearest Exit from Entrance in Maze

1926. Nearest Exit from Entrance in Maze

アプローチ

BFS

class Solution {
    public int[] dx = {1, 0, -1, 0};
    public int[] dy = {0, 1, 0, -1};
    public int height;
    public int width;
    public boolean[][] isVisited;
    public Queue<Point1926> q;
    public int result = Integer.MAX_VALUE;

    public int nearestExit(char[][] maze, int[] entrance) {

        height = maze.length;
        width = maze[0].length;
        isVisited = new boolean[height][width];

        q = new LinkedList<>();

        q.add(new Point1926(entrance[0], entrance[1], 0));
        isVisited[entrance[0]][entrance[1]] = true;


        while (!q.isEmpty()) {
            Point1926 now = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = dx[i] + now.x;
                int nextY = dy[i] + now.y;

                if (nextX < 0 || height <= nextX || nextY < 0 || width <= nextY) {
                    if (now.count == 0) {
                        continue;
                    }
                    result = Math.min(now.count, result);
                    continue;
                }

                if (isVisited[nextX][nextY] == true) {
                    continue;
                }

                if (maze[nextX][nextY] == '+') {
                    continue;
                }

                q.add(new Point1926(nextX, nextY, now.count + 1));
                isVisited[nextX][nextY] = true;


            }
        }
        return result == Integer.MAX_VALUE ? -1 : result;

    }
}

class Point1926 {
    int x;
    int y;
    int count;

    Point1926(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}