곰팡이
시간 제한2초메모리 제한128 MB
곰팡이 군집이 매일 성장 속도에 따라 확산하며(속도가 높은 종이 충돌 시 우선함) 모든 곰팡이가 하나로 합쳐질 때까지 걸리는 날수를 구하는 시뮬레이션 문제입니다.
문제
벽에 곰팡이가 자라고 있다. 처음에는 곰팡이가 여러 덩어리로 나뉘어 있으며, 시간이 지나 모두 하나의 덩어리가 되기까지 며칠이 걸리는지 구해야 한다.
벽은 m행 n열 격자로 나뉜다. 곰팡이가 있는 칸들은 가로 또는 세로로 인접해 있으면 같은 덩어리에 속한다.
처음에 같은 덩어리에 속한 곰팡이들은 모두 같은 종이며 자라는 속도도 같다. 서로 다른 덩어리에 속한 곰팡이는 종이 다를 수 있고, 자라는 속도도 다를 수 있다. 시간이 지나면서 서로 다른 종의 곰팡이 덩어리가 서로 닿아 하나의 덩어리가 될 수 있다.
자라는 속도가 k인 곰팡이는 하루가 지나면, 그 곰팡이가 있던 칸을 중심으로 한 (2k+1)행 (2k+1)열 정사각형 영역 전체에 같은 종의 곰팡이를 퍼뜨린다. 서로 다른 종의 곰팡이가 같은 칸으로 퍼지면, 자라는 속도가 더 빠른 곰팡이가 그 칸을 차지한다.
입력
첫째 줄에 벽의 크기를 나타내는 두 정수 m과 n이 주어진다. (1 <= m, n <= 100)
둘째 줄부터 m개의 줄에 벽의 상태가 한 행씩 주어진다. 곰팡이가 있는 칸은 그 곰팡이의 자라는 속도로 표시하고, 곰팡이가 없는 칸은 0으로 표시한다. 자라는 속도는 1 이상 5 이하의 정수이다. 각 행의 숫자 사이에는 공백이 없다.
출력
곰팡이가 모두 하나의 덩어리가 되기까지 걸리는 시간을 일 단위로 출력한다.
힌트
주어진 보이는 테스트에서 시간이 지남에 따라 벽의 상태는 다음과 같이 변한다.
222220000111111
222220000111111
222220111111111
222220111111111
222200111111111
222222201111111
222222211111111
222222211111111
222222211111111
222222211111111