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

문제

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

현재 상황은 마을 뒷산에서 전투가 일어나고 있고, 형의 나무가 불길을 막아서고 있어. 지도를 통해 살펴보면 마을 뒷산은 $N \times M$의 직사각형의 격자에 해당하는 형태임을 알 수 있지. 아, 지도의 밖은 돌로 둘러싸여 있어 불이 퍼질 수 없으니 걱정하지 마.

불은 상하좌우로 인접한 나무를 통해서만 퍼져나갈 수 있고, 어떤 날에서 그다음 날로 넘어갈 때, 각 불은 동시에 퍼지게 돼. 불과 접촉한 나무는 다음 날 전부 불에 타서 불길이 되어버려. 하지만, 돌이 있는 지역은 불이 붙지 않아. 

너도 알다시피 대피에는 시간이 굉장히 중요해. 우리는 주민들이 안전히 대피할 수 있도록 만날 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기를 구해야만 해. 불이 돌에 막혀 모든 불이 하나로 합쳐지지 않을 수도 있는데, 그럴 땐 합쳐질 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기의 합을 구하면 돼.

불이 합쳐진다는 것은 불이 다른 불과 상하좌우로 인접하게 되는 것을 뜻하고, 불의 크기는 불이 붙은 칸의 개수를 말해.

부탁해! 어서! 문제를 해결해서 우리 마을과 형에게 도움을 줘!

입력

첫 번째 줄에 지도의 크기를 나타내는 정수 $N,~ M$이 주어진다. ($1 \leq N, M \leq 2,000$)

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

출력

만날 수 있는 모든 불이 만나는 최소 시간과 그때의 불의 크기의 합을 출력한다. 첫날은 $0$일차이다. 즉, 처음부터 합칠 수 있는 모든 불이 합쳐져 있다면 최소 시간은 $0$이다.

만약 퍼질 불이 없다면, "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번