1162. As Far from Land as Possible - Explanation

class Solution:
    def maxDistance(self, grid: list[list[int]]) -> int:
        N = len(grid)
        direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def bfs(row, col):
            q = deque([(row, col)])
            visit = [[False] * N for _ in range(N)]
            dist, visit[row][col] = 0, True

            while q:
                dist += 1
                for _ in range(len(q)):
                    r, c = q.popleft()
                    for dx, dy in direct:
                        newR, newC = r + dx, c + dy
                        if min(newR, newC) < 0 or max(newR, newC) >= N or visit[newR][newC]:
                            continue
                        if grid[newR][newC] == 1:
                            return dist
                        visit[newR][newC] = True
                        q.append((newR, newC))
            return -1

        res = -1
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 0:
                    res = max(res, bfs(r, c))
                    if res == -1:
                        return res

        return res

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        q = deque()

        for r in range(N):
            for c in range(N):
                if grid[r][c]:
                    q.append([r, c])

        res = -1
        direct = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        while q:
            r, c = q.popleft()
            res = grid[r][c]

            for dr, dc in direct:
                newR, newC = r + dr, c + dc
                if min(newR, newC) >= 0 and max(newR, newC) < N and grid[newR][newC] == 0:
                    q.append([newR, newC])
                    grid[newR][newC] = grid[r][c] + 1

        return res - 1 if res > 1 else -1

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        direct = [0, 1, 0, -1, 0]
        visit = [[False] * N for _ in range(N)]
        q = deque()

        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    visit[r][c] = True
                    q.append((r, c))

        res = 0
        while q:
            res += 1
            for _ in range(len(q)):
                r, c = q.popleft()
                for d in range(4):
                    newR, newC = r + direct[d], c + direct[d + 1]
                    if 0 <= newR < N and 0 <= newC < N and not visit[newR][newC]:
                        q.append((newR, newC))
                        visit[newR][newC] = True

        return res - 1 if res > 1 else -1

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N, INF = len(grid), 10**6

        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    continue
                grid[r][c] = INF
                if r > 0:
                    grid[r][c] = min(grid[r][c], grid[r - 1][c] + 1)
                if c > 0:
                    grid[r][c] = min(grid[r][c], grid[r][c - 1] + 1)

        res = 0
        for r in range(N - 1, -1, -1):
            for c in range(N - 1, -1, -1):
                if grid[r][c] == 1:
                    continue
                if r < N - 1:
                    grid[r][c] = min(grid[r][c], grid[r + 1][c] + 1)
                if c < N - 1:
                    grid[r][c] = min(grid[r][c], grid[r][c + 1] + 1)
                res = max(res, grid[r][c])

        return res - 1 if res < INF else -1

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        res, INF = -1, 10**6
        dp = [[INF] * (N + 2) for _ in range(N + 2)]

        for r in range(1, N + 1):
            for c in range(1, N + 1):
                if grid[r - 1][c - 1] == 1:
                    dp[r][c] = 0
                else:
                    dp[r][c] = min(dp[r - 1][c], dp[r][c - 1]) + 1

        for r in range(N, 0, -1):
            for c in range(N, 0, -1):
                if grid[r - 1][c - 1] == 0:
                    dp[r][c] = min(dp[r][c], min(dp[r + 1][c], dp[r][c + 1]) + 1)
                    res = max(res, dp[r][c])

        return res if res < INF else -1