[leetcode] No 63. Unique Paths II Python Solution
[Problem]
You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 10^9.
[Explanation]
It is upgrade? version of No. 62.
The goal is to find the number of paths to reach to bottem-right corner with minimum path.
But, there are obtacles in the map.
1) I change the obtacles, which are 1, to -1 not to be confused.
2) I do like leet code no. 2. But, if I check there is -1 nearby.
For example, map[row][col] = map[row - 1][col] + map[row][col - 1] if map[row - 1][col] and map[row][col - 1] aren't -1.
Threfore, there are four conditions like
There is visual example.
| 0 | 0 | 1 -> -1 | 0 |
| 0 | 0 | 1 -> -1 | 0 |
| 0 | 0 | 0 | 0 |
| 0 (start) | 1 | -1 | 0 |
| 1 | 2 | -1 | 0 |
| 1 | 3 | 3 | 3 (ans) |
[Solution]
- complexity: O(n^2)
|
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
row = len(obstacleGrid)
col = len(obstacleGrid[0])
if row == 1 and col == 1 and obstacleGrid[0][0] == 0:
return 1
if obstacleGrid[0][0] == 1 or obstacleGrid[row - 1][col - 1] == 1:
return 0
for i in range(0, row):
for j in range(0, col):
if obstacleGrid[i][j] == 1:
obstacleGrid[i][j] = -1
for i in range(1, row):
if obstacleGrid[i][0] == -1: break
obstacleGrid[i][0] = 1
for j in range(1, col):
if obstacleGrid[0][j] == -1: break
obstacleGrid[0][j] = 1
for i in range(1, row):
for j in range(1, col):
if obstacleGrid[i][j] == -1: continue
if obstacleGrid[i][j - 1] == -1 and obstacleGrid[i - 1][j] == -1:
obstacleGrid[i][j] = 0
elif obstacleGrid[i][j - 1] == -1 and obstacleGrid[i - 1][j] != -1:
obstacleGrid[i][j] = obstacleGrid[i - 1][j]
elif obstacleGrid[i][j - 1] != -1 and obstacleGrid[i - 1][j] == -1:
obstacleGrid[i][j] = obstacleGrid[i][j - 1]
else:
obstacleGrid[i][j] = obstacleGrid[i -1][j] + obstacleGrid[i][j - 1]
return obstacleGrid[row - 1][col - 1]
|
#leetcode #coding test #coding stduy #array #dynamic programming #algorithm #python #solution