迷路的机器人

回溯

直接回溯会超时，dfs 的时候加一个 visited 标识一般是为了防止死循环，但这个题目只能向右向下走，所以不会死循环，所以很多人就不加 visited 了。

但其实这个题目仍然需要 visited 标识，因为我们可以通过不同的路径到达同一个位置：比如身处位置 (0,0) 时，可以通过”先右再下”和“先下再右”两种方式到达 (1,1)。

使用 visited 就可以确保那些“已被试过无法到达目标”的位置不会再次被尝试，从而提升效率，避免超时。

class Solution {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        boolean[][] vis = new boolean[obstacleGrid.length][obstacleGrid[0].length];
        if (obstacleGrid == null) return new ArrayList<>();
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return new ArrayList<>();
        backtrack(obstacleGrid, 0, 0, new ArrayList<>(),vis);
        return resList;
    }

    List<List<Integer>> resList = new ArrayList<>();

    public boolean backtrack(int[][] obstacleGird, int y, int x, List<List<Integer>> list, boolean[][] vis) {
        if (y >= obstacleGird.length || y < 0 || x < 0 || x >= obstacleGird[0].length || obstacleGird[y][x] == 1||vis[y][x]) {
            return false;
        }
        if (y == obstacleGird.length - 1 && x == obstacleGird[0].length - 1 && obstacleGird[y][x] == 0) {
            list.add(Arrays.asList(y, x));
            resList = new ArrayList<>(list);
            return true;
        }

        if (obstacleGird[y][x] == 0) {
            vis[y][x] = true;
            list.add(Arrays.asList(y, x));
            if (backtrack(obstacleGird, y + 1, x, list, vis)) return true;
            if (backtrack(obstacleGird, y, x + 1, list, vis)) return true;
            list.remove(list.size() - 1);
        }
        return false;
    }
 
}

动态规划

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {

        int row = obstacleGrid.length;
        if (row == 0) {
            return res;
        }
        int col = obstacleGrid[0].length;
        if (col == 0) {
            return res;
        }

        // 起点或终点是障碍，不可能到达
        if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
            return res;
        }

        int dp[][] = new int[row+1][col+1];
        dp[0][0] = 1;
        // 初始化首列
        for (int i = 1; i < row; i++) {
            if (obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        // 初始化首行
        for (int i = 1; i < col; i++) {
            if (obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
            } else {
                dp[0][i] = dp[0][i - 1];
            }
        }
        // 求路径
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else { // 无需保存和，保存最大的即可
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 到达终点的路径为0，直接返回
        if (dp[row - 1][col - 1] == 0) {
            return res;
        }

        // 从终点反推回起点
        int r = row - 1, c = col - 1;
        while (r != 0 || c != 0) {
            res.add(Arrays.asList(r,c));

            int up = 0;
            if (r > 0) {
                up = dp[r - 1][c];
            }

            int left = 0;
            if (c > 0) {
                left = dp[r][c - 1];
            }

            if (up >= left) {
                r--;
            } else {
                c--;
            }
        }
        res.add(Arrays.asList(0,0));
        Collections.reverse(res);
        return res;
    }
}

user83429423的评论

赏

谢谢你请我吃糖果

微信