[Leetcode] 1162. As Far from Land as Possible

https://leetcode.com/problems/as-far-from-land-as-possible/description/

initial

q staright forward we just do multi-source BFS starting from all land cells simultaneously (not dfs cuz we will be exploring grid fully multiple times)

sol

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n,m=len(grid),len(grid[0])
        queue=[]
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1:
                    queue.append((i,j))
        moves=[[1,0],[-1,0],[0,1],[0,-1]]
        while queue:
            cur_x,cur_y=queue.pop(0)
            for move in moves:
                next_x,next_y=cur_x+move[0],cur_y+move[1]
                if 0<=next_x<n and 0<=next_y<m and grid[next_x][next_y]==0:
                    grid[next_x][next_y]=grid[cur_x][cur_y]+1
                    queue.append((next_x,next_y))
        ans=-1
        for i in range(n):
            for j in range(m):
                ans=max(ans,grid[i][j])
        if ans==0 or ans==1:
            return -1
        else:
            return ans-1

complexity

n^2 time cuz queue explores every grid cell
n^2 space grid