1162. As Far from Land as Possible

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if(m == 0 or n == 0) return -1;

        queue<pair<int, int>> q;
        vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    q.push({i, j});
                }
            }
        }

        if(q.size() == m * n) return -1;

        int ans = 0;

        while(not q.empty()) {
            int s = q.size();
            ans++;

            while(s--) {
                auto cur = q.front(); q.pop();
                int x = cur.first, y = cur.second;

                for(auto &dir : dirs) {
                    int dx = x + dir.first, dy = y + dir.second;
                    if(dx >= 0 and dx < m and dy >= 0 and dy < m and grid[dx][dy] == 0) {
                        q.push({dx, dy});
                        grid[dx][dy] = 1;
                    }
                }
            }
        }

        return ans - 1;
    }
};

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = []
        vis = [[False] * n  for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if(grid[i][j] == 1):
                    q.append((i, j))
                    vis[i][j] = True

        lvl = 0
        while(q):
            s = len(q)
            
            while(s):
                x, y = q[0][0], q[0][1]
                q.pop(0)
                
                for i in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                    
                    dx, dy = x + i[0], y + i[1]
                    
                    if(dx >= 0 and dx < n and dy >= 0 and dy < n and not vis[dx][dy]):
                        grid[dx][dy] = lvl
                        q.append((dx, dy))
                        vis[dx][dy] = True
                        
                s -= 1
            lvl += 1

        return lvl - 1 if lvl > 1 else -1