1162. As Far from Land as Possible | 1666

 1class Solution:
 2    def maxDistance(self, grid: List[List[int]]) -> int:
 3        # bfs from every water source is bad
 4        # took the hint
 5        # try bfs from every land
 6
 7        # KEY TAKEAWAYS for multi-source BFS:
 8        # In BFS you loop only if you keep re-visiting nodes.
 9        # So the rule of thumb is:
10        # ✅ Mark a node as visited at the moment you enqueue it — not when you dequeue it.
11
12        q = deque()
13        n = len(grid)
14        result = 0
15        visited = set()
16
17        for i in range(n):
18            for j in range(n):
19                if grid[i][j] == 1:
20                    q.append((i, j, 0))  # loc_x, loc_y, manhattan distance to water
21
22        while q:
23            i, j, dist = q.popleft()
24
25            if dist > result:
26                result = dist
27
28            # right
29            right = (i, j + 1)
30            if j + 1 < n and right not in visited and grid[i][j + 1] == 0:
31                visited.add(right)
32                q.append((i, j + 1, dist + 1))
33            # down
34            down = (i + 1, j)
35            if i + 1 < n and down not in visited and grid[i + 1][j] == 0:
36                visited.add(down)
37                q.append((i + 1, j, dist + 1))
38            # left
39            left = (i, j - 1)
40            if j - 1 > -1 and left not in visited and grid[i][j - 1] == 0:
41                visited.add(left)
42                q.append((i, j - 1, dist + 1))
43            # up
44            up = (i - 1, j)
45            if i - 1 > -1 and up not in visited and grid[i - 1][j] == 0:
46                visited.add(up)
47                q.append((i - 1, j, dist + 1))
48
49        return result if result > 0 else -1