1888번 - 곰팡이

벽에 곰팡이가 자라고 있다. 곰팡이들은 현재 여러 개의 덩어리를 이루고 있는 상태인데, 이들이 점점 자라나서 한 덩어리로 될 때까지 얼마의 시간이 걸릴지 알고 싶다. 이를 계산하는 프로그램을 작성해 보자.

곰팡이가 피어 있는 벽은 m행 n열의 격자로 나뉘어 있고, 한 칸 당 한 개의 곰팡이가 있다. 곰팡이의 덩어리라는 것은, 격자 상에 가로세로로 인접한 곰팡이들의 집합을 말한다.

맨 처음 상태에서는 한 덩어리 안의 곰팡이들이 모두 같은 종으로, 자라는 속도도 같다. 그러나 서로 다른 덩어리에 속한 곰팡이는 종이 달라 자라는 속도도 다를 수 있다. 또, 시간이 지남에 따라 서로 다른 종의 곰팡이 덩어리가 한 덩어리로 합쳐지는 경우도 있을 수 있다. 만약 어느 곰팡이의 자라는 속도가 k라면, 하루가 지났을 때 그 곰팡이가 피어있던 자리를 중심으로 2k+1행 2k+1열의 격자에 같은 종의 곰팡이가 번진다는 의미이다. 만약 서로 다른 종의 곰팡이가 같은 칸에 번져 오면, 자라는 속도가 빠른 곰팡이가 그 칸을 차지한다.

첫 줄에 곰팡이가 피어 있는 벽의 크기를 나타내는 두 정수 m과 n이 주어진다. (1 ≤ m, n ≤100) 둘째 줄부터는 벽의 상황이 한 줄에 한 행씩 주어진다. 곰팡이가 피어있는 곳은 그 곰팡이의 자라는 속도로, 그렇지 않은 곳은 0으로 표시되어 있다. 자라는 속도는 1이상 5이하의 정수이다. 각 숫자 사이에는 빈 칸이 없다.

첫 줄에 곰팡이가 한 덩어리가 되기까지 걸리는 시간을 하루 단위로 출력한다.

입출력 예시에서, 시간이 지남에 따라 달라지는 벽의 모습을 차례대로 나타내면 다음과 같다.

222220000111111
222220000111111
222220111111111
222220111111111
222200111111111

222222201111111
222222211111111
222222211111111
222222211111111
222222211111111