14271번 - 그리드 게임

크기가 무한대이고 단위 정사각형으로 나누어져있는 그리드가 있다. 그리드의 칸은 살아있거나 죽어있다.

매초마다 모든 칸의 상태는 아래와 같은 규칙을 통해서 바뀐다.

• 칸 C와 변을 인접한 네 개의 칸 중에서 적어도 한 칸이 살아있으면, C는 1초 후에도 살아있다. 그 외의 경우에는 죽어있다.
• 모든 칸은 동시에 변한다.

처음 그리드의 상태가 주어졌을 때, K초가 지난 후에 총 몇 개의 칸이 살아있는지 구하는 프로그램을 작성하시오.

첫째 줄에 처음 그리드의 행의 개수 N과 열의 개수 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에는 처음 그리드의 상태가 주어진다. 살아있는 칸은 'o'로, 죽어있는 칸은 '.'으로 주어진다.

마지막 줄에는 K (1 ≤ K ≤ 1500)가 주어진다.

첫째 줄에 K초가 지난 후에 살아있는 칸의 개수를 출력한다.

예제 1의 경우에 3초가 지난 후의 모습은 아래와 같다.

...oo...
..oooo..
.oooooo.
oooooooo
ooooooo.
.ooooo..
..ooo...
...o....