시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB60212044.444%

문제

난 나뭇잎 마을의 초대 호카게인 센쥬 하시라마의 동생, 센쥬 토비라마라고 한다. 지금 우리 마을은 크나큰 위기에 빠져있다. 우리와 끊기지 않는 악연을 지닌 우치하 가문의 수장인 우치하 마다라가 구미를 끌고 마을을 습격했기 때문이지. 형은 호카게로서 마다라와 전투를 벌이고 있고 마을 주민들에게 피해가 갈까 봐 제대로 전투하지 못하고 있어. 지금 놈의 화둔이 마을로 넘어오지 못하게 우리 형의 목둔이 막아주고 있으니 나무가 크게 불타기 전에 미리 주민들을 대피 시켜야 해. 우리 형이 나뭇잎 마을을 지키려면 네 도움이 필요해. 

지금 현재 상황은 마을 뒷산에서 전투가 일어나고 있고, 형의 나무가 불길을 막아서고 있어. 지도를 통해 살펴보면 n x m의 직사각형에 해당하는 면적임을 알 수 있지.

불과 접촉한 나무는 다음 날 전부 불에 타서 불길이 되어버려. 그러니 불은 상하좌우로 인접한 나무를 통해서만 퍼져나갈 수 있어. 

하지만, 돌이 있는 지역에는 불이 지나갈 수가 없어. 그러니 모든 불이 하나로 합쳐지지 않을 수도 있는데, 그럴 땐 합쳐질 수 있는 경우까지의 최소 시간과 불의 크기를 구하면 돼. 

너도 알겠지만 대피에는 시간이 굉장히 중요하단 걸 알고 있을 거야. 우리는 주민들이 안전히 대피할 수 있게 만날 수 있는 모든 불이 모두 만나는 최소 시간과 그 때의 불의 크기를 구해야만 해. 부탁해! 얼른! 문제를 해결해서 우리 마을과 형에게 도움을 줘!

입력

첫 번째 줄에 n, m이 주어진다. (1 ≤ n, m ≤ 2,000)

두 번째 줄부터 n + 1번째 줄까지 0, 1, 2로 이루어진 첫 날 지도가 표시된다. (불 = 0, 나무 = 1, 돌 = 2)

출력

만날 수 있는 모든 불이 만나는 최소 시간과 그 때의 불의 크기를 출력하시오.

만약 퍼질 불이 없다면, "0 0" 을 출력하시오.

예제 입력 1

5 11
00111110100
01111110111
01111111110
11110011111
11000000111

예제 출력 1

2 53

예제 입력 2

5 6
011112
201120
022211
111101
111111

예제 출력 2

2 20

예제 입력 3

3 3
111
101
111

예제 출력 3

0 1

힌트

지도의 밖은 물로 둘러쌓여 있어, 불과 나무가 넘어갈 수 없다. 나무는 아예 움직이지 않고, 불로 뒤덮이는 경우를 제외하고선 변하지 않는다. 

돌은 불의 영향을 받지 않는다. 즉, 돌이 있는 지역으로 불이 갈 수 없다. 또한, 돌은 움직이지 않는다. 

어떤 날에서 그 다음 날로 넘어갈 때, 각 불은 한 번에 퍼지게 된다. 

출처

University > 경북대학교 > 2021 Goricon H번