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 &lt; n &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 &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>};