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
58
59
60
61
62
63
64
65
66
67
68
69
70

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];
                    if(CheckIn(x+1,y,p_c,top) == false)
                    {
                        p_c[top].x = x+1;
                        p_c[top++].y = y;
                    }
                }
                if(y + 1 < n && 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 < top;i++)
            {
                p[i].x = p_c[i].x;
                p[i].y = p_c[i].y;
            }
        }
        return obstacleGrid[m-1][n-1];
    }
};