|
题目：和上一题类似，就是这个时候给定了矩阵包含0和1,1代表不能从这里走。我的想法其实很明确，还是用动态规划，只是碰到壁垒的时候要进行考虑。还有初始化很重要。
因为1本来是要用来代表在这里出发到终点有一种可能的，所以壁垒的1要用其他代替，我用-1代表是壁垒。
如果给定的数组第一个数就是1，那永远都出发不了，那就是返回0种可能。如果有且仅有一个数那就返回1。之后考虑在不止一个数的情况。如图：
假设原来的数组为：
那么初始化后应该是：
之后就判断i和j都从1开始，并且是从左边一个数和上一个数的和，但是有三种可能
1.如果本身就是1，那么直接赋值-1，因为不能从这里过
2.如果左边是-1，那么就把当前的赋值为上面的
3.如果上面的是-1，那么就把当前的赋值为左边的
如上例子应该为：
代码如下：
复制代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid)
{
// if(obstacleGrid.size() < 1) return 1;
if(obstacleGrid[0][0] == 1) return 0;
if(obstacleGrid.size() == 1 && obstacleGrid[0].size()==1) return 1;
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
int i = 1, j = 1;
while(j<n && obstacleGrid[0][j] != 1) obstacleGrid[0][j++]=1;
while(j<n) obstacleGrid[0][j++] = -1;
while(i<m && obstacleGrid[i][0] != 1) obstacleGrid[i++][0]=1;
while(i<m) obstacleGrid[i++][0] = -1;
for (i = 1; i < m; ++i)
for (j = 1; j < n; ++j)
{
if (obstacleGrid[i][j] == 1)
{
obstacleGrid[i][j] = -1;
continue;
}
int left = obstacleGrid[i][j-1], up = obstacleGrid[i-1][j];
if (left != -1 && up != -1)
obstacleGrid[i][j] = left + up;
else if (left == -1)
obstacleGrid[i][j] = up;
else
obstacleGrid[i][j] = left;
}
if (obstacleGrid[m-1][n-1] == -1)
return 0;
return obstacleGrid[m-1][n-1];
}
|
