You are given an integer matrix isWater of size m x n that represents a map of land and water cells.


	If isWater[i][j] == 0, cell (i, j) is a land cell.
	If isWater[i][j] == 1, cell (i, j) is a water cell.


You must assign each cell a height in a way that follows these rules:


	The height of each cell must be non-negative.
	If the cell is a water cell, its height must be 0.
	Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).


Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

&nbsp;
Example 1:



Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.


Example 2:



Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.


&nbsp;
Constraints:


	m == isWater.length
	n == isWater[i].length
	1 &lt;= m, n &lt;= 1000
	isWater[i][j] is 0 or 1.
	There is at least one water cell.


class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        arr = collections.deque()
        m, n = len(isWater), len(isWater[0])
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    arr.append((0, i, j))
                    
        ans = [[-1] * n for _ in range(m)]
        while arr:
            val, x, y = arr.popleft() 
            if ans[x][y] != -1: continue
            ans[x][y] = val
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                xx, yy = x+dx, y+dy
                if 0 <= xx < m and 0 <= yy < n and ans[xx][yy] == -1:
                    arr.append((val+1, xx, yy))
        return ans
class Solution {
    
    static int[][] DIRECTION = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    int rows;
    int cols;
    int[][] isWater;

    
    public int[][] highestPeak(int[][] isWater) {
        this.isWater = isWater;
        rows = isWater.length;
        cols = isWater[0].length;
        

        int[][] heightCells = new int[rows][cols];
        
        //store the coordinate of water cell
        Queue<int[]> queue = new LinkedList();
        
        for(int r = 0; r < rows; r++){
            for(int c = 0; c < cols; c++){
                if(isWater[r][c] == 1){
                    
                    //mark as water
                    heightCells[r][c] = 0;
                    
                    //add water coordinate
                    queue.add(new int[]{r, c});
                } else{
                    //mark default value for land
                    heightCells[r][c] = -1;  
                }
            }
        }

        
        /*
        * Approach
        * 1. start from every water source, 
             update their neighbor height
        * 2. add each neighbours which was not processed earlier
          3. do it every cell is processed
        */
        bfs(queue, heightCells);
        
        
        return heightCells;
    }
    
    private void bfs(Queue<int[]> queue, int[][] heightCells){
        
        while(!queue.isEmpty()){
            int[] cell = queue.remove();
 
            //increment height of neighbor cell in all 4 direction 
            //e.g, left, right, up, down
            for(int[] dir : DIRECTION){
                
                int newRow = cell[0] + dir[0];
                int newCol = cell[1] + dir[1]; 
                
                //check new coordinate of cell inside the grid or not
                if(!isInsideGrid(newRow, newCol)) continue;
                
                //check already handled
                if(heightCells[newRow][newCol] != -1) continue;

                //increament, 
                heightCells[newRow][newCol] =  heightCells[cell[0]][cell[1]] + 1;
                
                //to handle the neighbour of this new cell
                queue.add(new int[]{newRow, newCol});
            }
        
        }
    }
    
    private boolean isInsideGrid(int row, int col){
        return row >= 0 && row < rows && col >= 0 && col < cols;
    } 
}
class Solution {
public:

    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int r = isWater.size();
        int c = isWater[0].size();
        queue <pair<int,int>> curr;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                //set the land cell to -1 (not visited)
                if (isWater[i][j] == 0) {
                    isWater[i][j] = -1;
                }
                //set the water cell to zero and to queue
                else {
                    isWater[i][j] = 0;
                    curr.push({i, j});
                }
            }
        }

        int hill = 0;
        while (!curr.empty()) {
            int len = curr.size();

            for (int k = 0; k < len; k++) {

                //for each cell check its 4 boundary cells
                //if it is not visited, increase its hill by 1
                pair <int, int> fnt = curr.front(); curr.pop();
                int i = fnt.first, j = fnt.second;

                //top cell
                if (i > 0 && isWater[i - 1][j] == -1) {
                    isWater[i - 1][j] = hill + 1;
                    curr.push({i-1, j});
                }
                //bottom cell
                if ((i < r - 1) && (isWater[i + 1][j] == -1)) {
                    isWater[i + 1][j] = hill + 1;
                    curr.push({i+1, j});
                }
                //left cell
                if (j > 0 && (isWater[i][j - 1] == -1)) {
                    isWater[i][j - 1] = hill + 1;
                    curr.push({i, j-1});
                }
                //right cell
                if ((j < c - 1) && (isWater[i][j + 1] == -1)) {
                    isWater[i][j + 1] = hill + 1;
                    curr.push({i, j+1});
                }
            }

            //after 1 complete round increase the height of the hill
            hill += 1;
        }

        return isWater;
    }
};
var highestPeak = function(isWater) {
    const RN = isWater.length, CN = isWater[0].length;
    const output = [...Array(RN)].map(() => Array(CN).fill(-1));
    const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    let queue = []

    for(let r = 0; r < RN; r++) {
        for(let c = 0; c < CN; c++) {
            if(isWater[r][c]) {
                queue.push([r, c]);
                output[r][c] = 0;
            }
        }
    }

    while(queue.length) {
        const next = []

        for(let [r, c] of queue) {
            for(let [dr, dc] of dir) {
                dr += r;
                dc += c;
                if(dr < 0 || dc < 0 || dr >= RN || dc >= CN || output[dr][dc] !== -1) continue;
                output[dr][dc] = output[r][c] + 1;
                next.push([dr, dc]);
            }
        }
        queue = next;
    }
    return output;
};
Map of Highest Peak