1003. Map of Highest Peak (BFS)

Given a grid isWater where 1 marks a water cell and 0 marks land, assign each cell a non-negative height so that every water cell has height 0, adjacent cells (4-directionally) differ in height by at most 1, and the maximum height is as large as possible. Return any such height matrix (the canonical one is each cell's distance to the nearest water cell). The input is JSON {isWater}.

Input: JSON {isWater}.

Output: Nested array — the height matrix.

Examples

Input: {"isWater":[[0,1],[0,0]]}
Output: [[1,0],[2,1]]
Explanation: Heights grow away from water.

Input: {"isWater":[[1]]}
Output: [[0]]
Explanation: Single water cell.

Input: {"isWater":[[0,0],[0,0]]}
Output: [[0,0],[0,0]]
Explanation: All water.

Constraints

• 1<=rows,cols<=1000
• at least one water cell

Asked by