class Solution:
    def islandsAndTreasure(self, grid: List[List[int]]) -> None:

        n, m = len(grid), len(grid[0])
        from collections import deque
        q = deque()
        visited = set()

        for r in range(n):
            for c in range(m):
                if grid[r][c] == 0:
                    q.append((r, c))
                    visited.add((r, c))


        dist = 0

        while(q):
            lenq = len(q)
            for i in range(lenq):
                (row, col) = q.popleft()

                grid[row][col] = dist
                directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
                for (dr, dc) in directions:
                    r, c = row+dr, col+dc

                    if (r in range(n) and
                        c in range(m) and
                        (r, c) not in visited and
                        grid[r][c]!=-1
                    ):
                        visited.add((r, c))
                        q.append((r, c))

            dist += 1

"""
 Time Complexity:

Complexity analysis

Time complexity : O(mn)O(mn)O(mn).

If you are having difficulty to derive the time complexity, start simple.

Let us start with the case with only one gate. The breadth-first search takes at most m×nm \times nm×n steps to reach all rooms, therefore the time complexity is O(mn)O(mn)O(mn). But what if you are doing breadth-first search from kkk gates?

Once we set a room's distance, we are basically marking it as visited, which means each room is visited at most once. Therefore, the time complexity does not depend on the number of gates and is O(mn)O(mn)O(mn).

Space complexity : O(mn)O(mn)O(mn).
The space complexity depends on the queue's size. We insert at most m×nm \times nm×n points into the queue.

"""