게걸스러운 곰팡이
면접 대비시간 제한3초메모리 제한512 MB
r×c 격자에 주어진 곰팡이가 매 단계마다 8방향 이웃으로 퍼지며 격자 밖으로도 자라날 때, k단계 뒤 차지하는 칸 수를 구한다.
문제
당신은 페트리 접시 재배를 통한 숨 막히게 아름다운 농업 연구소의 저명한 연구원으로서, 미래의 식량이 될지도 모르는 새로운 생물을 찾고 있다. 최근 영양가가 높고 음식에서 얻은 에너지를 몸무게로 바꾸는 효율이 매우 뛰어난 곰팡이형 생물을 발견했다. 음식으로 둘러싸인 작은 배양체를 페트리 접시에 놓고 잠시 성장하는 모습을 지켜보았다.
하지만 주말이 되었으니, 이 페트리 접시 속 내용물을 계속 들여다보는 것보다(비록 재미있는 녀석이긴 하지만) 사랑하는 사람들과 시간을 보내고 싶다. 필요한 조치를 취하지 않고 떠날 수는 없다. 곰팡이가 너무 커져서 연구소의 나머지 부분을 먹어치우기 시작하면 어떡하나?
상황을 다음과 같이 모델링한다. 평면을 1 × 1 정사각형으로 나누고, 곰팡이가 현재 있는 위치를 표시한다. 매 시간 단계마다 곰팡이가 어떤 정사각형을 차지하고 있으면, 그 정사각형의 여덟 개 이웃 정사각형 모두로 확장된다(그리고 원래 정사각형도 계속 차지한다). 주말 동안 몇 시간 단계가 지나갈지 알고 있으니, 돌아왔을 때 곰팡이가 차지하는 정사각형의 수를 알고 싶다.
그림 G.1: 곰팡이 성장의 예시. 샘플 2의 곰팡이를 0, 1, 2 시간 단계 후에 나타낸 것이다. 가운데 그림이 샘플 2의 정답 출력에 해당한다.
참고: 입력에서 곰팡이는 유한한 격자 위에 주어지지만, 그 경계를 넘어 성장할 수 있고 실제로 성장한다. 곰팡이는 그렇게 쉽게 가둬지지 않는다.
입력
- 첫째 줄에 정수 1 ≤ r, c ≤ 20과 0 ≤ k ≤ 106이 주어진다. r과 c는 초기 격자의 행과 열의 수이고, k는 시간 단계의 수이다.
- 그다음 r개의 줄에 걸쳐 c개의 문자가 주어지며, 각 문자는 ‘.’ 또는 ‘#’이다. ‘#’은 곰팡이가 이 정사각형을 차지하고 있음을 나타낸다. 곰팡이는 연결되어 있지 않아도 된다.
출력
- k 시간 단계가 지난 후 곰팡이가 차지하는 정사각형의 수를 출력한다.