Informatica Online Judge

  모래 성 [1208 / 04B8]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 28   Total Tried : 29


The Champion of this Problem (C++) : t1234 - 0ms / 606byte
My Best Submission (C++) : N/A

[JOI(2014/2015예선)]

Background

경곽이는 가족과 함께 해안으로 놀러 온 경곽이는 가족과 함께 열심히 수영을 하여 피곤해졌다.

경곽이는 다음으로 해변에서 모래성을 쌓기 시작했다. 잠시 모래 장난을 한 경곽이는 다시 만든 성을 방치하고 바다로 수영하러 갔다.

경곽이가 만든 성은 직사각형 영역으로 이루어져 있다.

이 직사각형 영역은 상하좌우의 격자형태로 구분할 수 있다.

각 칸은 경곽이가 만든 성의 일부를 이루는 칸과, 그렇지 않은 평지 칸으로 구분할 수 있다.

각각의 성을 이루는 칸은 강도가 1이상 9이하의 값을 가진다.

직사각형 영역의 바깥 테두리 부분에는 성을 이루는 칸은 존재하지 않는다.

잠시 후 바다가 만조가 되어 직사각형 영역에 파도가 밀려오게 되었다.

파디고 한 번 밀려 올 때마다 성의 칸들 중 다음 조건을 만족하는 모든 칸이 일제히 붕괴되어 평지로 바뀐다.

조건 : 주변의 8칸에 있는 평지 칸의 수가 해당 칸의 강도보다 같거나 클 경우.

파도가 지나간 후 바로 다음 파도가 밀려온다.

충분히 많은 파도를 맞은 후, 성이 모두 붕괴될지 일부가 남아 있을지, 즉, 파도가 밀려오더라도 성을 이루는 부분이 하나도 파괴되지 않는 상태가 될 때까지 파도를 맞은 횟수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 성의 영역의 크기를 나타내는 정수 h와 w가 공백으로 구분되어 입력된다.

h는 모래 성의 영역의 행, w는 모래 성의 영역의 열을 나타낸다. (이 부분의 테두리는 모두 평지로 되어 있음을 보장한다.)

다음 줄부터 h줄에 걸쳐서 2개의 문자열이 입력된다. 문자열은 "1"~"9"까지의 성의 강도를 나타내는 값 또는 평지를 나타내는 값 "."중 하나의 문자로 이루어진다.

[입력값의 정의역]
3 <= h, w <= 1,000

Output

성이 없어지거나 더 이상 붕괴되지 않는 상태가 될 때까지 맞은 파도의 횟수를 출력한다.

IO Example

입력
5 6
......
.939..
.3428.
.9393.
......

출력
3

* 설명 :

입력예일 경우 첫 번째 파도를 맞을 때 아래 그림과 같이 강도가 3인 모든 성은 붕괴된다.
......
.9.9..
..428.
.9.9..
......

다음 파도를 맞고 난 후는 강도가 2인 성이 붕괴된다.

......
.9.9..
..4.8.
.9.9..
......

다음 파도를 맞고 난 후는 강도가 4인 성이 붕괴된다.

......
.9.9..
....8.
.9.9..
......

이제 더 이상의 파도를 맞더라도 성은 붕괴되지 않으므로 최종 상태가 된다.

따라서 총 맞은 파도의 횟수는 3회이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]