Unique Paths II: Navigating Obstacles

Imagine you are a robot tasked with navigating a grid. Your goal is to reach the bottom-right corner from the top-left corner. However, this grid is not empty; it contains obstacles that the robot cannot pass through. This challenge requires you to count the number of distinct paths the robot can take, considering these impassable obstacles. This is a common problem in robotics and pathfinding algorithms, crucial for efficient task planning in constrained environments.

Problem Description

You are given a 2D grid representing a map. Each cell in the grid can either be an empty space (represented by 0) or an obstacle (represented by 1). You start at the top-left cell (grid[0][0]) and want to reach the bottom-right cell (grid[rows-1][cols-1]).

The robot can only move in two directions: either down or right.

Your task is to calculate the total number of unique paths from the start to the end, avoiding any cells that contain obstacles.

Key Requirements:

• The robot must start at grid[0][0].
• The robot must end at grid[rows-1][cols-1].
• The robot can only move down or right.
• The robot cannot enter any cell marked as an obstacle (1).
• If the start or end cell is an obstacle, there are no valid paths.

Expected Behavior:

The function should return an integer representing the number of unique paths.

Edge Cases to Consider:

• A grid with no obstacles.
• A grid where the start or end cell is an obstacle.
• A grid with only one row or one column.
• A grid where all cells are obstacles.

Examples

Example 1:

Input:
grid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]

Output:
2

Explanation: There are two unique paths to reach the bottom-right corner:

1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

The path Down -> Right -> Down -> Right is blocked by the obstacle at grid[1][1].

Example 2:

Input:
grid = [
  [0, 1],
  [0, 0]
]

Output:
1

Explanation: The only valid path is Down -> Right. The path Right -> Down is blocked by the obstacle at grid[0][1].

Example 3:

Input:
grid = [
  [1, 0]
]

Output:
0

Explanation: The starting cell grid[0][0] is an obstacle, so no paths are possible.

Constraints

• 1 <= rows, cols <= 100 (where rows is the number of rows and cols is the number of columns in the grid)
• grid[i][j] is either 0 (empty space) or 1 (obstacle).
• The solution should aim for an efficient time complexity.

Notes

This problem can be effectively solved using dynamic programming. Consider how the number of paths to reach a certain cell is related to the number of paths to reach the cells from which it is reachable. Think about how obstacles affect these calculations.