Problem: A robot is located at the top-left corner(0, 0) of a m x n grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner (m -1, n-1) of the grid.
Now consider if some obstacles are added to the grids. How many unique paths would there be?
public static int UniquePathsWithObstacles(int[][] obstacleGrid)
{
if (obstacleGrid == null || obstacleGrid.Length == 0)
{
return 0;
}
int m = obstacleGrid.Length;
int n = obstacleGrid[0].Length;
int[,] count = new int[m, n];
count[0, 0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 1; i < m; ++i)
{
if (obstacleGrid[i][0] == 0)
{
count[i, 0] = count[i - 1, 0];
}
}
for (int i = 1; i < n; ++i)
{
if (obstacleGrid[0][i] == 0)
{
count[0, i] = count[0, i -1];
}
}
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
if (obstacleGrid[i][j] == 0)
{
count[i, j] = count[i, j - 1] + count[i - 1, j];
}
}
}
return count[m - 1, n - 1];
}
No comments:
Post a Comment