Simulate Water Flow

Water starts at a given cell, which becomes wet at time 0. At each step, water spreads simultaneously to the up, down, left, and right neighbors whose height does not exceed the current cell's. Return the time each cell first becomes wet; cells that can never be reached are −1.

This site has made the standard input and output explicit.

输入格式

The first line contains n m startRow startCol, followed by n lines of m heights, 0-indexed. On this site 1≤n,m≤500 and heights are in −10⁹..10⁹.

输出格式

Output the first-wet times as n rows of m columns.

样例 1

输入：

3 3 1 1
3 2 1
6 5 4
9 8 7

输出：

-1 1 2
-1 0 1
-1 -1 -1

样例 2

输入：

4 4 1 2
10 10 10 10
10 10 10 10
10 10 10 10
10 10 10 10

输出：

3 2 1 2
2 1 0 1
3 2 1 2
4 3 2 3

样例 3

输入：

1 1 0 0
0

输出：

0

样例说明

Example 1: from 5, water first reaches the 2 above and the 4 to the right, then the 1; the other cells are higher and unreachable, so the output matches the matrix in the statement. Example 2: water can flow between equal heights, so every time equals the Manhattan distance to (1,2). Example 3: a single starting cell has time 0.