모래성 - 구름LEVEL
모래성
Quiz Info
모래성
100points
Participant
4
Solved Rate
0%
0
1

문제


바닷게 놀러 간 구름이는 모래사장에서 모래 섬을 만들었다. 구르미는 자신이 만든 모래 섬에 다리를 세우고 싶어한다. 다리를 그냥 만들 수 있지만, 다리는 섬과 섬을 이어줄 때 그 의미가 있다고 생각을 했다. 구르미는 섬을 만들기 위해서 모래사장에 물을 붇기로 한다. 모래 섬은 주변에 물이 있으면 무너져 내린다.

현재 모래사장은 세로의 길이가 , 가로의 길이가  크기이다. 모래사장을  크기로 나누었을 때, 가장 왼쪽 위부터 번째 줄의 번재 칸을 라고 표현할 수 있다.

의 값이 이라면 이미 물에 가라앉았다는 의미이다.  이 양의 정수라면, 현재 위치의 모래의 고도이다. 모래는 주변의 물의 양에 따라서 매 분마다 무너져 내린다.  의 상태가 모래라면, 모래사장 안에서  , ,의 상태에 영향 받는다. 곳의 상태 중 하나라도 물이 있다면, 물인 상태의 개수만큼 모래는 무너져 내린다. 모래의 고도는 이하로 떨어지지 않으며, 곳의 상태가 모두 모래라면 모래의 고도는 낮아지지 않는다.

매 분마다 위의 과정이 반복된다. 위의 과정을 통해서 모래 섬이 개의 이상의 섬으로 나누어지면 다리를 건설할 수 있는 상태이다. 구름이가 물을 부은 뒤 몇 분이 뒤에 다리를 건설 할 수 있는지 출력하시오. 단, 다리를 건설할 수 없거나, 이미 나누어져 있다면 을 출력하시오. 


입력


첫째 줄에 모래사장의 크기 이 공백을 두고 주어진다.

둘째 줄부터 줄에 걸쳐서 현재 모래사장의 상태가 주어진다. 번째 줄의 번째 수는 의 값이며, 각 숫자는 공백을 두고 주어진다. 은 이상 이하의 정수이다.


출력


구름이가 물을 부은 뒤, 몇 분 후 다리를 건설할 수 있는지 출력하시오. 다리를 건설할 수 없거나, 이미 섬이 2개로 나누어져 있다면 을 출력하시오.

Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
33
010
030
000
Output
0
Example 2
Input
33
520
070
000
Output
2
⋇ Please keep the input and output formats carefully
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions (0)