[LeetCode] 迷宫问题(The Maze)

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 8.6k 阅读时长 ≈ 8 分钟

By Long Luo

490. 迷宫 Medium
505. 迷宫 II Medium 499. 迷宫 III Hard

490. The Maze

490 The Maze
490 The Maze

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

        int m = maze.length;
        int n = maze[0].length;

        if (m * n <= 2) {
            return true;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);

        boolean[][] visited = new boolean[m][n];
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();

            int x = curPos[0];
            int y = curPos[1];

            if (x == destination[0] && y == destination[1]) {
                return true;
            }

            for (int[] dir : dirs) {
                int nextX = x + dir[0];
                int nextY = y + dir[1];

                while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0) {
                    nextX += dir[0];
                    nextY += dir[1];
                }

                if (!visited[nextX - dir[0]][nextY - dir[1]]) {
                    visited[nextX - dir[0]][nextY - dir[1]] = true;
                    queue.offer(new int[]{nextX - dir[0], nextY - dir[1]});
                }
            }
        }

        return false;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;

        if (m * n <= 2) {
            return true;
        }

        boolean[][] visited = new boolean[m][n];
        return dfs(maze, visited, start, destination);
    }

    private static boolean dfs(int[][] maze, boolean[][] visited, int[] start, int[] destination) {
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

        if (start[0] == destination[0] && start[1] == destination[1]) {
            return true;
        }

        int m = maze.length;
        int n = maze[0].length;

        visited[start[0]][start[1]] = true;
        boolean result = false;

        for (int[] dir : dirs) {
            int nextX = start[0] + dir[0];
            int nextY = start[1] + dir[1];

            while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0) {
                nextX += dir[0];
                nextY += dir[1];
            }

            nextX -= dir[0];
            nextY -= dir[1];

            if (visited[nextX][nextY]) {
                continue;
            }

            if (dfs(maze, visited, new int[]{nextX, nextY}, destination)) {
                result = true;
                break;
            }
        }

        return result;
    }
}

505. The Maze II

505 The Maze II
505 The Maze II 2

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

        int m = maze.length;
        int n = maze[0].length;

        if (m * n <= 2) {
            return 1;
        }

        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1]});

        distance[start[0]][start[1]] = 0;

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();

            int x = curPos[0];
            int y = curPos[1];

            for (int[] dir : dirs) {
                int nextX = x + dir[0];
                int nextY = y + dir[1];

                int stepCnt = 0;

                while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0) {
                    nextX += dir[0];
                    nextY += dir[1];
                    stepCnt++;
                }

                if (distance[nextX - dir[0]][nextY - dir[1]] > distance[x][y] + stepCnt) {
                    distance[nextX - dir[0]][nextY - dir[1]] = distance[x][y] + stepCnt;
                    queue.offer(new int[]{nextX - dir[0], nextY - dir[1]});
                }
            }
        }

        return distance[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]];
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;

        if (m * n <= 2) {
            return 1;
        }

        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }

        distance[start[0]][start[1]] = 0;
        dfs(maze, distance, start);

        return distance[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]];
    }

    private static void dfs(int[][] maze, int[][] distance, int[] start) {
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

        int m = maze.length;
        int n = maze[0].length;

        for (int[] dir : dirs) {
            int nextX = start[0] + dir[0];
            int nextY = start[1] + dir[1];
            int steps = 0;

            while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0) {
                nextX += dir[0];
                nextY += dir[1];
                steps++;
            }

            nextX -= dir[0];
            nextY -= dir[1];

            if (distance[nextX][nextY] > distance[start[0]][start[1]] + steps) {
                distance[nextX][nextY] = distance[start[0]][start[1]] + steps;
                dfs(maze, distance, new int[]{nextX, nextY});
            }
        }
    }
}

499. The Maze III

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        String[] actions = {"u", "d", "l", "r"};

        int m = maze.length;
        int n = maze[0].length;

        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }

        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < m * n; i++) {
            map.put(i, "");
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{ball[0], ball[1]});

        distance[ball[0]][ball[1]] = 0;

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();

            int x = curPos[0];
            int y = curPos[1];
            int dist = distance[x][y];

            for (int i = 0; i < 4; i++) {
                int nextX = x;
                int nextY = y;

                String path = map.get(x * n + y);
                int steps = 0;

                while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0
                        && !(nextX == hole[0] && nextY == hole[1])) {
                    nextX += dirs[i][0];
                    nextY += dirs[i][1];
                    steps++;
                }

                if (!(nextX == hole[0] && nextY == hole[1])) {
                    nextX -= dirs[i][0];
                    nextY -= dirs[i][1];
                    steps--;
                }

                path += actions[i];

                if (dist + steps < distance[nextX][nextY]) {
                    distance[nextX][nextY] = dist + steps;
                    map.put(nextX * n + nextY, path);

                    if (!(nextX == hole[0] && nextY == hole[1])) {
                        queue.offer(new int[]{nextX, nextY});
                    }
                } else if (dist + steps == distance[nextX][nextY] && path.compareTo(map.get(nextX * n + nextY)) < 0) {
                    map.put(nextX * n + nextY, path);
                    if (!(nextX == hole[0] && nextY == hole[1])) {
                        queue.offer(new int[]{nextX, nextY});
                    }
                }
            }
        }

        String res = map.get(hole[0] * n + hole[1]);
        return res.equals("") ? "impossible" : res;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length;
        int n = maze[0].length;

        int[][] distance = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }

        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < m * n; i++) {
            map.put(i, "");
        }

        distance[ball[0]][ball[1]] = 0;
        dfs(maze, distance, map, ball[0], ball[1], hole);

        String res = map.get(hole[0] * n + hole[1]);
        return res.equals("") ? "impossible" : res;
    }

    private static void dfs(int[][] maze, int[][] distance, Map<Integer, String> map, int x, int y, int[] hole) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        String[] actions = {"u", "d", "l", "r"};

        int m = maze.length;
        int n = maze[0].length;

        for (int i = 0; i < 4; i++) {
            int nextX = x;
            int nextY = y;
            int stepCnt = 0;

            String path = map.get(x * n + y);

            while (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && maze[nextX][nextY] == 0
                    && !(nextX == hole[0] && nextY == hole[1])) {
                nextX += dirs[i][0];
                nextY += dirs[i][1];
                stepCnt++;
            }

            if (nextX != hole[0] || hole[1] != nextY) {
                nextX -= dirs[i][0];
                nextY -= dirs[i][1];
                stepCnt--;
            }

            path += actions[i];

            if (distance[nextX][nextY] > distance[x][y] + stepCnt) {
                distance[nextX][nextY] = distance[x][y] + stepCnt;
                map.put(nextX * n + nextY, path);
                if (nextX != hole[0] || nextY != hole[1]) {
                    dfs(maze, distance, map, nextX, nextY, hole);
                }
            } else if (distance[nextX][nextY] == distance[x][y] + stepCnt && path.compareTo(map.get(nextX * n + nextY)) < 0) {
                map.put(nextX * n + nextY, path);
                if (nextX != hole[0] || nextY != hole[1]) {
                    dfs(maze, distance, map, nextX, nextY, hole);
                }
            }
        }
    }
}

参考文献

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗