Description

The cave map is represented by an $R \times C$ character matrix:

• . means an empty cell with no explorer at the beginning; an empty cell can hold any number of explorers.
• P means an empty cell with an explorer at the beginning. We assume that initially all explorers are in distinct cells, and no explorer is initially on an exit cell.
• * means an obstacle; explorers cannot pass through cells occupied by obstacles.
• O (capital letter O) means an exit. The input guarantees that every exit lies on the boundary of the map, i.e., O can appear only in row $1$, row $R$, column $1$, or column $C$.

Additionally, the input guarantees that the entire map is enclosed by boundary and exits, i.e., in row $1$, row $R$, column $1$, and column $C$, only * or O may appear.

Input Format

The first line contains two integers $R$ and $C$ separated by a space, denoting the size of the map. The second line contains the integer $T$, the time until the cave collapses. The next $R$ lines each contain $C$ characters, describing a cave map.

Output Format

Output one line containing a single integer, the maximum number of explorers that can escape within $T$ time units.

5 5
4
*****
*P..*
O**.O
*P..*
*****

1

Hint

The cave has two exits, but only the right exit is reachable. Although in $3$ time units both people can reach the cell to the left of the exit, because at most one person can pass through the exit per time unit, only one person can escape within $4$ time units. Both can escape in $5$ time units.

• For $30\%$ of the testdata, the numbers of explorers and exits are both at most $10$.
• For $100\%$ of the testdata, $3 \le R, C \le 12$, $0 < T \le 50$.

Translated by ChatGPT 5