체스판 위의 공
면접 대비시간 제한2초메모리 제한512 MB
R×C 체스판의 각 칸에 서로 다른 정수가 적혀 있고, 공은 인접한 8칸 중 가장 작은 수가 적힌 칸으로 계속 이동하다가 주변보다 작은 칸에서 멈춘다. 각 칸에 최종적으로 몇 개의 공이 남는지 구한다.
문제
크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀 있다. 체스판에 적혀 있는 정수는 모두 서로 다르다.
체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음 규칙에 따라 자동으로 움직인다.
- 인접한 8방향(가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다.
- 그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다.
공의 크기는 매우 작아서 체스판의 한 칸 위에 여러 개의 공이 있을 수 있다. 체스판의 상태가 주어진다. 공이 더 이상 움직이지 않을 때, 각 칸에 공이 몇 개 있는지 구해 보자.
입력
첫째 줄에 체스판의 크기 R, C가 주어진다. 둘째 줄부터 R개의 줄에 체스판에 적혀 있는 정수가 주어진다.
출력
총 R개의 줄에 걸쳐서 체스판에 적힌 정수를 출력한다.
제한
- 1 ≤ R, C ≤ 500
- 0 ≤ 체스판에 적힌 정수 ≤ 300,000