首页 » 编程之美 » 正文

[leetcode_63]Unique Paths II

Unique Paths
http://blog.sina.com.cn/s/blog_672f71fc0101pf1c.html 的变形。加入障碍物,判断一下即可。

struct PPoint
{
    int x;
    int y;
};
class Solution {
public:
    bool CheckIn(int x,int y,PPoint *p,int top)
    {
        for(int i = 0;i < top;i++)
        {
            if(x == p[i].x && y == p[i].y)
            {
                return true;
            }
        }
        return false;
    }
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        if(m <= 0 )return 0;
        int n = obstacleGrid[0].size();
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1)return 0;
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++)
                if(obstacleGrid[i][j] == 1)obstacleGrid[i][j] = -1;
        PPoint *p = new PPoint[m+n];
        PPoint *p_c = new PPoint[m+n];
        int index = 0;
        p[index].x = 0;
        p[index++].y = 0;
        obstacleGrid[0][0] = 1;
        while(true)
        {
            int top = 0;
            for(int i = 0;i < index;i++)
            {
                int x = p[i].x;
                int y = p[i].y;
                if(x + 1 < m && obstacleGrid[x+1][y] != -1)
                {
                    obstacleGrid[x+1][y] += obstacleGrid[x][y];</p>

<pre><code>                if(CheckIn(x+1,y,p_c,top) == false)
                {
                    p_c[top].x = x+1;
                    p_c[top++].y = y;
                }
            }
            if(y + 1 &amp;lt; n &amp;amp;&amp;amp; obstacleGrid[x][y+1] != -1)
            {
                obstacleGrid[x][y+1] += obstacleGrid[x][y];
                if(CheckIn(x,y+1,p_c,top) == false)
                {
                    p_c[top].x = x;
                    p_c[top++].y = y+1;
                }
            }
        }
        if(top == 0)
            break;
        index = top;
        for(int i = 0;i &amp;lt; top;i++)
        {
            p[i].x = p_c[i].x;
            p[i].y = p_c[i].y;
        }
    }
    return obstacleGrid[m-1][n-1];
}
</code></pre>

<p>};

发表评论