from collections import deque
from heapq import heappop, heappush
from itertools import product
from sys import maxsize
cellT = tuple[int, int]
countT = int
class Solution1:
def shortestPathBinaryMatrix(self, grid: list[list[int]]):
cellsT = set[cellT]
N = len(grid)
dummy_start_cell = (-1, -1)
bottom_right_cell = (N - 1, N - 1)
def find_adjacents(curr_row: int, curr_col: int):
def is_valid(cand_cell: cellT):
cand_row, cand_col = cand_cell
return (
0 <= cand_row < N
and 0 <= cand_col < N
and grid[cand_row][cand_col] == 0
)
cand_cells = (
(curr_row + row_offset, curr_col + col_offset)
for row_offset, col_offset in product(range(-1, 2), repeat=2)
)
return filter(is_valid, cand_cells)
queue: deque[cellsT] = deque([{dummy_start_cell}])
visiteds: cellsT = set()
count: countT = 1
while queue:
next_: cellsT = set()
q: cellsT = queue.popleft()
for cell in q:
visiteds.add(cell)
for adjacent in find_adjacents(*cell):
if adjacent in visiteds:
continue
if adjacent == bottom_right_cell:
return count
next_.add(adjacent)
if next_:
queue.append(next_)
count += 1
return -1
class Solution2:
def shortestPathBinaryMatrix(self, grid: list[list[int]]):
N = len(grid)
dummy_start_cell = (-1, -1)
bottom_right_cell = (N - 1, N - 1)
def find_adjacents(curr_row: int, curr_col: int):
def is_valid(cand_cell: cellT):
cand_row, cand_col = cand_cell
return (
0 <= cand_row < N
and 0 <= cand_col < N
and grid[cand_row][cand_col] == 0
)
cand_cells = (
(curr_row + row_offset, curr_col + col_offset)
for row_offset, col_offset in product(range(-1, 2), repeat=2)
)
return filter(is_valid, cand_cells)
heap: list[tuple[countT, cellT]] = [(0, dummy_start_cell)]
visiteds: set[cellT] = set()
while heap:
cost, vertex = heappop(heap)
if vertex == bottom_right_cell:
return cost
for new_vertex in find_adjacents(*vertex):
if new_vertex in visiteds:
continue
visiteds.add(new_vertex)
new_cost = cost + 1
heappush(heap, (new_cost, new_vertex))
return -1
class Solution3:
def shortestPathBinaryMatrix(self, grid: list[list[int]]):
N = len(grid)
dummy_start_cell = (-1, -1)
bottom_right_cell = (N - 1, N - 1)
def find_adjacents(curr_row: int, curr_col: int):
def is_valid(cand_cell: cellT):
cand_row, cand_col = cand_cell
return (
0 <= cand_row < N
and 0 <= cand_col < N
and grid[cand_row][cand_col] == 0
)
cand_cells = (
(curr_row + row_offset, curr_col + col_offset)
for row_offset, col_offset in product(range(-1, 2), repeat=2)
)
return filter(is_valid, cand_cells)
def heuristic(cell_row: int, cell_col: int):
return max(abs(N - 1 - cell_row), abs(N - cell_col))
heap: list[tuple[countT, countT, cellT]] = [(-maxsize, 0, dummy_start_cell)]
costs: dict[cellT, countT] = {}
while heap:
estimate, cost, vertex = heappop(heap)
if vertex == bottom_right_cell:
return cost
for new_vertex in find_adjacents(*vertex):
new_cost = cost + 1
if costs.get(new_vertex, maxsize) > new_cost:
costs[new_vertex] = new_cost
new_estimate = new_cost + heuristic(*new_vertex)
heappush(heap, (new_estimate, new_cost, new_vertex))
return -1