643. Map of Highest Peak

Given a grid isWater where 1 marks water and 0 land, assign each cell a height so that water cells are height 0, adjacent cells differ by at most 1, and the maximum height is as large as possible. Return any valid height matrix (the one produced by BFS from water). The input is JSON {isWater}.

Input: JSON {isWater}.

Output: Array — the height of each cell.

Examples

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

Input: {"isWater":[[0,0,1],[1,0,0],[0,0,0]]}
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: BFS distances from water.

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

Constraints

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

Asked by