Leetcode(63) Unique Paths II

发表于 | 更新于 | 分类于

Description:

A robot is located at the top-left corner of a _m_ x _n_ grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: _m_ and _n_ will be at most 100.

Example 1: Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

解法：

首先考虑采用队列进行解题（毕竟迷宫地图类常用套路0.0），然而在矩阵较小时挺好，遇上大矩阵就超时了。以下为该方法代码：

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        Queue<pointposition> queue = new LinkedList<pointposition>();
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        if (row == 1 && col == 1) {
            return 1;
        }
        int result = 0;
        pointposition start = new pointposition(0, 0);
        pointposition end = new pointposition(row - 1, col - 1);
        queue.offer(start);
        while (queue.peek() != null) {
            pointposition now = queue.poll();
            if (now.equal(end)) {
                result += 1;
                continue;
            }
            pointposition next1 = new pointposition(now.posx + 1, now.posy);
            pointposition next2 = new pointposition(now.posx, now.posy + 1);
            if (judge(next1, row, col) && obstacleGrid[next1.posx][next1.posy] != 1) {
                queue.offer(next1);
            }
            if (judge(next2, row, col) && obstacleGrid[next2.posx][next2.posy] != 1) {
                queue.offer(next2);
            }
        }
        return result;
    }

    Boolean judge(pointposition x, int row, int col) {
        if (x.posx >= 0 && x.posx < row && x.posy >= 0 && x.posy < col) {
            return true;
        }
        return false;
    }
}

class pointposition {
    public int posx;
    public int posy;

    pointposition(int x, int y) {
        this.posx = x;
        this.posy = y;
    }

    boolean equal(pointposition x) {
        if (this.posx == x.posx && this.posy == x.posy) {
            return true;
        }
        return false;
    }
}

考虑到在这种情形下，无论从起点到终点还是从终点到起点，路径的数目是一样的。我们可以按照每一个点到起点的路径数逆推得到终点到起点的路径数。对于起点，起点到起点的路径数为1.对于其他点，它们到起点的路径数一定等于在它上方的点到起点的路径数与在它左方的点到起点的路径数之和，因为这个点只能通过它的上方和左方两个方向到达起点。简而言之，采用动态规划的方法解题，该问题的状态转移函数为：

1
nums(i , j) = nums(i , j-1) + nums(i-1 , j)

需要注意的是，本题中存在障碍物，对于障碍物的点，显然，它到起点的路径数为0。AC动态规划代码如下：

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        if (row == 1 && col == 1) {
            return 1;
        }
        int[][] tmp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    tmp[i][j] = 0;
                } else if (i == 0 && j == 0) {
                    tmp[i][j] = 1;
                } else if (i == 0 && j > 0) {
                    tmp[i][j] = tmp[i][j - 1];
                } else if (j == 0 && i > 0) {
                    tmp[i][j] = tmp[i - 1][j];
                } else {
                    tmp[i][j] = tmp[i - 1][j] + tmp[i][j - 1];
                }
            }
        }
        return tmp[row - 1][col - 1];
    }
}