Under construction

Still being built. Things may change

Ball on a Chessboard

Interview

Time limit2sMemory limit512 MB

Summary
Each cell of an R by C board holds a distinct number; every ball rolls to the smallest neighbor until it reaches a local minimum, and we must count how many balls stop on each cell.
Level

Medium6 of 10

Topics
Graph, Dynamic programming, DFS, Matrix
Solved
No attempts yet

Problem

There is a chessboard of size R×C, and each cell of the chessboard has one integer written on it. All integers written on the chessboard are distinct.

Place one ball on each cell of the chessboard. The balls now move automatically according to the following rules.

  • If every integer written in the 8 adjacent directions (horizontal, vertical, diagonal) is greater than the number written in the current cell, the ball stops moving.
  • Otherwise, the ball moves to the cell with the smallest integer.

Balls are very small, so a cell of the chessboard may contain several balls. The state of the chessboard is given. Find how many balls are on each cell when the balls no longer move.

Input

The first line gives the size of the chessboard, R and C. From the second line, R lines give the integers written on the chessboard.

Output

Print the integers written on the chessboard over R lines in total.

Constraints

  • 1 ≤ R, C ≤ 500
  • 0 ≤ integer written on the chessboard ≤ 300,000

Examples3

  1. Example 1

    Input
    3 3
1 3 4
5 6 7
8 9 2
    Expected output
    6 0 0
0 0 0
0 0 3

  2. Example 2

    Input
    1 6
10 20 3 4 5 6
    Expected output
    1 0 5 0 0 0

  3. Example 3

    Input
    4 4
20 2 13 1
4 11 10 35
3 12 9 7
30 40 50 5
    Expected output
    0 4 0 4
0 0 0 0
4 0 0 0
0 0 0 4