LeetCode OJ--Unique Paths II **

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

图的深搜，有障碍物，有的路径不通。

刚开始想的时候用组合数算，但是公式没有推导出来。

于是用了深搜，递归调用。

但是图最大是100*100，太大了，超时。考虑到在计算（2,1）和（1,2）都用到了(2，2)，也就是说有了重复计算。于是记录这些中间的数据。

而有的地方因为有障碍物，所以得的路径值是0，这又要和没有计算做个区分，于是又加了些数据，标志是否已经计算过了。

class Solution {

public:

    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {

        if(obstacleGrid.size() == )

            return ;

        int row = obstacleGrid.size();

        int col = obstacleGrid[].size();

        //the destination position unavailable

        if(obstacleGrid[row-][col-] ==  || obstacleGrid[][] ==)

            return ;

        vector<vector<bool> > handled; //to mark if xy has handled

        vector<vector<int> > tempRecord;

        handled.resize(row);

        tempRecord.resize(row);

        for(int i = ;i<row;i++)

        {

            tempRecord[i].resize(col);

            handled[i].resize(col);

            for(int j = ;j<col;j++)

                handled[i][j] = false; // all initialized false

        }

        int ans = calcPath(obstacleGrid,,,row,col,tempRecord,handled);

        //no path

        if(ans <  )

            ans = ;

        return ans;

    }

    int calcPath(vector<vector<int> > &grid ,int xPos, int yPos,int row,int col,vector<vector<int> > &tempRecord,vector<vector<bool> > &handled)

    {

        //destination

        if(xPos == row - && yPos == col - )

            return ;

        //unhandle this position

        if(tempRecord[xPos][yPos] ==  && handled[xPos][yPos] == false)

        {

            int ans = ;

            if(xPos < row- && grid[xPos + ][yPos] ==)

                if(handled[xPos+][yPos] == false)

                    ans = calcPath(grid,xPos+,yPos,row,col,tempRecord,handled);

                else

                    ans = tempRecord[xPos+][yPos];

            if(yPos < col - && grid[xPos][yPos+] == )

                //unhandled

                if(handled[xPos][yPos+] == false)

                    ans += calcPath(grid,xPos,yPos+,row,col,tempRecord,handled);

                else

                    ans += tempRecord[xPos][yPos+];

            tempRecord[xPos][yPos] = ans;

        }

        handled[xPos][yPos] = true;

        return tempRecord[xPos][yPos];

    }

};

巴特西

LeetCode OJ--Unique Paths II **

最新文章

热门文章