leet weekly 295-4

# https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/
from collections import deque

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        # 0-1 bfs
        y_max, x_max = len(grid), len(grid[0])
        d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        distance = [[-1] * x_max for _ in range(y_max)]
        q = deque([(0, 0, 0)])

        while q:
            dist, r, c = q.popleft()
            for dr, dc in d:
                y, x = r + dr, c + dc
                if 0 <= y < y_max and 0 <= x < x_max and distance[y][x] == -1:
                    if grid[y][x] == 0:
                        distance[y][x] = dist
                        q.appendleft((dist, y, x))
                    else:
                        distance[y][x] = dist + 1
                        q.append((dist + 1, y, x))
                    if y == y_max - 1 and x == x_max - 1:
                        return distance[-1][-1]
        return distance[-1][-1]