Problem Statement

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Example 1:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

Problem Link

Code (Using BFS)

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        
        int n = grid.size();
        int res = -1;
        
        queue<pair<int,int>> q;
       
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    
                    q.push({i,j});
                    
                }
               
            }
        }
        
        if(q.size()==0 || q.size()==n*n)
            return -1;
        
        vector<int> dx{-1,0,1,0};
        vector<int> dy{0,1,0,-1};
        int depth = 0;
        
        while(!q.empty())
        {
            int lsize = q.size();
            depth++;
            
            while(lsize--)
            {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                
                for(int k=0;k<4;k++)
                {
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if(nx<0||ny<0||nx>n-1||ny>n-1||grid[nx][ny])
                        continue;
                    
                    grid[nx][ny] = depth;
                    q.push({nx,ny});
                }
            }
            
            
        }
        
        return depth-1;
    }
    
};