Problem

Base On The Maze, we wanna get the shortest path from start point to the end point

思路一(dijkstra algorithm)

• 从当前点计算到临近点的路径
• 然后选最小的路径走 （所以需要PriorityQueue，而不是Queue）
• 需要有一个int[][] 数组记录每个点距离起点的最小距离， 一旦当前点的路径长度大于已有的距离，pass
• 不需要boolean的visited数组，因为一个点可能会被访问多次

    /**
        dijkstra中， 一个点可能会被访问多次， 所以不能用visited数组
        但是在这个点可能被访问的n次当中， 我们需要得出最小值， 所以需要一个数组去记录所有的点他们的路径长度
    */

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int m = maze.length;
        int n = maze[0].length;
        PriorityQueue<Point> queue = new PriorityQueue<>(1, (p1, p2) -> p1.len - p2.len);
        int[][] res = new int[maze.length][maze[0].length];
        for (int i = 0; i < m * n; i++) res[i / n][i % n] = Integer.MAX_VALUE;
        queue.offer(new Point(start[0], start[1], 0));

        while (!queue.isEmpty()) {
            Point curt = queue.poll();
            if (curt.x == destination[0] && curt.y == destination[1]) return curt.len;
            if (res[curt.x][curt.y] <= curt.len) continue;
            res[curt.x][curt.y] = curt.len;
            for (int dir = 0; dir < 4; dir++) {
                int x = curt.x;
                int y = curt.y;
                int l = curt.len;
                while (!touchWall(maze, x + dx[dir], y + dy[dir])) {
                    x += dx[dir];
                    y += dy[dir];
                    l++;
                }
                queue.offer(new Point(x, y, l));
            }
        }
        return -1;
    }

    private boolean touchWall(int[][] maze, int x, int y) {
        if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] == 1) return true;
        return false;
    }

思路二（dfs）

写法一（TLE）

• 我的想法是起始点到终点的最短距离 = （起始点到周围点的距离 + 周围点到终点的最短距离）中的最短距离

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m * n; i++) res[i / n][i % n] = Integer.MAX_VALUE;
        int ans = dfs(maze, start, destination, new boolean[m][n]);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    private int dfs (int[][] maze, int[] start, int[] destination, boolean[][] visited) {
        if (Arrays.equals(start, destination)) return 0;

        if (visited[start[0]][start[1]]) return Integer.MAX_VALUE;
        int ans = Integer.MAX_VALUE;
        visited[start[0]][start[1]] = true;
        for (int i = 0; i < 4; i++) {
            int x = start[0];
            int y = start[1];
            int path = 0;

            while (canRoll(maze, x + dx[i], y + dy[i])) {
                x += dx[i];
                y += dy[i];
                path++;
            }
            if(x == start[0] && y == start[1]) continue;
            int next = dfs(maze, new int[]{x, y}, destination, visited);
            if (next != Integer.MAX_VALUE) {
                path += next;
                ans = Math.min(ans, path);
            }

        }
        visited[start[0]][start[1]] = false;
        return ans;
    }

    private boolean canRoll(int[][] maze, int x, int y) {
        if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] == 1) return false;
        return true;
    }

写法二（traverse）

• 计算每个点离起点最短距离

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        int[][] res = new int[m][n];
        res[start[0]][start[1]] = 1;
        dfs(maze, start, destination, res);
        return res[destination[0]][destination[1]] - 1;
    }

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    private void dfs (int[][] maze, int[] start, int[] destination, int[][] res) {
        if (Arrays.equals(start, destination)) return;

        for (int i = 0; i < 4; i++) {
            int x = start[0];
            int y = start[1];
            int path = res[x][y];
            while (canRoll(maze, x + dx[i], y + dy[i])) {
                x += dx[i];
                y += dy[i];
                path++;
            }
            if (res[x][y] != 0 && res[x][y] <= path) continue;
            res[x][y] = path;
            dfs(maze, new int[]{x, y}, destination, res);
        }
    }

    private boolean canRoll(int[][] maze, int x, int y) {
        if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] == 1) return false;
        return true;
    }
}