Grid Game

Interview

Time limit2sMemory limit512 MB

Summary

Each cell becomes alive if it or an edge neighbor was alive, so the live region grows by repeated dilation; count live cells after K steps.

Level: Medium6 of 10
Topics: Simulation, BFS, Matrix, Implementation
Solved: No attempts yet

Problem

An infinite grid is divided into unit square cells. Every cell is either alive or dead.

Every second all cells change state at the same time, by this rule.

Take the five cells made of $C$ itself and the four cells that share an edge with $C$ . If at least one of them is alive, then $C$ is alive one second later.
Otherwise $C$ is dead one second later.

Given the starting state of the grid, write a program that counts how many cells are alive after $K$ seconds.

Input

The first line contains the number of rows $N$ and the number of columns $M$ of the rectangular area whose starting state is given. ( $1 \le N, M \le 50$ )

Each of the next $N$ lines contains $M$ characters describing the starting state of that area. An alive cell is o and a dead cell is .. Every cell outside the area is dead at the start.

The last line contains $K$ . ( $1 \le K \le 1500$ )

Output

Print the number of alive cells after $K$ seconds.

Note

Suppose the starting state is the one below and $K = 3$ .

oo
o.

After 3 seconds the grid looks like this.

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

Examples3

Example 1
Input
```
2 2
oo
o.
3
```
Expected output
```
36
```
Example 2
Input
```
2 2
..
..
23
```
Expected output
```
0
```
Example 3
Input
```
1 1
o
1000
```
Expected output
```
2002001
```