시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 38 17 11 50.000%

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

2 2
oo
o.
3

예제 출력 1

36

예제 입력 2

2 2
..
..
23

예제 출력 2

0

예제 입력 3

1 1
o
1000

예제 출력 3

2002001

힌트

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

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

출처