陈中正的网络日志

LeetCode: Unique Paths II

题目

https://oj.leetcode.com/problems/unique-paths-ii/

分析

这道题是Unique Paths的变形,只是稍微复杂了一点。

1.

在Unique Paths中, paths[i][j] = paths[i-1][j] + paths[i][j-1];

在Unique Paths II中,在这句之前要加一个判断语句来判断obstacleGrid[i][j]的值是否为1,如果是1则将paths[i][j]直接赋值为0

  1. 仅仅做完第一步还不行,原本第一行都为1,

现在如果第一行某个元素是obstacle,那么这一行该元素及其之后的元素路径数都为0,为什么呢?

因为要想如Unique Paths中所说路径长度达到最小,那么第一行obstacle之后的元素必然不能走。

第一列也是同样的道理。

代码

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> paths(m, vector<int>(n, 1));

        int firstRowFirstObstacle = -1;
        int firstColFirstObstacle = -1;
        //get first obstacle position in first col and first row 
        for (int i = 0; i < m; i++)
            if (obstacleGrid[i][0] == 1)
            {
                firstColFirstObstacle = i;
                break;
            }
        for (int i = 0; i < n; i++)
            if (obstacleGrid[0][i] == 1)
            {
                firstRowFirstObstacle = i;
                break;
            }

        //assign 0 where firstObstacle and after that in first row and col
        if (firstColFirstObstacle != -1)
            for (int i = firstColFirstObstacle; i < m; i++)
                paths[i][0] = 0;
        if (firstRowFirstObstacle != -1)
            for (int i = firstRowFirstObstacle; i < n; i++)
                paths[0][i] = 0;

        //calculate paths
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (obstacleGrid[i][j] == 1)
                {
                    paths[i][j] = 0;
                    continue;
                }
                paths[i][j] = paths[i-1][j] + paths[i][j-1];
            }
        }

        return paths[m-1][n-1];
    }
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40865761

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40866417

Categories:  OJ题解 

« LeetCode: Minimum Path Sum LeetCode: Unique Paths »