Сложность: hard
Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:
1, представляющая начальную клетку. Существует ровно одна начальная клетка.
2, представляющая конечную клетку. Существует ровно одна конечная клетка.
0, представляющая пустые клетки, по которым можно ходить.
-1, представляющая препятствия, по которым нельзя ходить.
Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.
Пример:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
👨💻 Алгоритм:
1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.
2⃣Для задачи обратного отслеживания можно сказать, что существует тысяча реализаций обратного отслеживания на тысячу людей, как будет видно из дальнейшей реализации.
3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.
😎 Решение:
class Solution:
def uniquePathsIII(self, grid: list[list[int]]) -> int:
def backtrack(row, col, remain):
if grid[row][col] == 2 and remain == 1:
self.path_count += 1
return
temp = grid[row][col]
grid[row][col] = -4
remain -= 1
for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
next_row, next_col = row + ro, col + co
if 0 <= next_row < self.rows and 0 <= next_col < self.cols and grid[next_row][next_col] >= 0:
backtrack(next_row, next_col, remain)
grid[row][col] = temp
non_obstacles = 0
start_row = start_col = 0
self.rows, self.cols = len(grid), len(grid[0])
for row in range(self.rows):
for col in range(self.cols):
if grid[row][col] >= 0:
non_obstacles += 1
if grid[row][col] == 1:
start_row, start_col = row, col
self.path_count = 0
backtrack(start_row, start_col, non_obstacles)
return self.path_count
Ставь 👍 и забирай 📚 Базу знаний