Unique Paths II with Obstacles

You are given an \( m \times n \) grid called obstacleGrid, where each cell is either free (represented by 0) or blocked by an obstacle (represented by 1). A robot is initially positioned at the top-left corner of the grid and wants to reach the bottom-right corner. The robot can only move either down or right at any step.

Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner while avoiding obstacles. If either the starting or the destination cell is blocked, the answer is 0.

inputFormat

The first line contains two integers ( m ) and ( n ), representing the number of rows and columns respectively. The next ( m ) lines contain ( n ) integers each (either 0 or 1), separated by spaces, denoting the grid.

outputFormat

Output a single integer which is the number of unique paths from the top-left corner to the bottom-right corner.## sample

1 1
0

1