"不同的路径" 的跟进问题:
现在考虑网格中有障碍物,那样将会有多少条不同的路径?
网格中的障碍和空位置分别用 1 和 0 来表示.
注意事项
m 和 n 均不超过 100
样例
如下所示在 3x3 的网格中有一个障碍物:
一共有 2 条不同的路径从左上角到右下角.
[[0,0,0],
[0,1,0],
[0,0,0]
]
class Solution {
public:
/*
* @param obstacleGrid: A list of lists of integers
* @return: An integer
*/
int uniquePathsWithObstacles(vector<vector<int>> &a) {
// write your code here
int row=a.size();
int col=a[0].size();
if(row==1)
return 1;
if(a[row-1][col-1]==1)
return 0;
if(a[0][0]==1)
return 0;
bool flag=true;
for(int i=0;i<col;i++)
{
if(a[0][i]==0&&flag)
a[0][i]=1;
else if(a[0][i]==1)
{
a[0][i]=-1;
flag=false;
}
}
flag=true;
for(int i=1;i<row;i++)
{
if(a[i][0]==0&&flag)
a[i][0]=1;
else if(a[i][0]==1)
{
a[i][0]=-1;
flag=false;
}
}
for(int i=1;i<row;i++)
{
for(int j=1;j<col;j++)
{
if(a[i][j]==1)
{
a[i][j]=-1;
continue;
}
int top=a[i-1][j];
int left=a[i][j-1];
if(top==-1)
{
top=0;
}
if(left==-1)
{
left=0;
}
a[i][j]=top+left;
}
}
return a[row-1][col-1];
}
};
来源: http://www.bubuko.com/infodetail-2477754.html