P3851 [TJOI2007] Escape

A group of explorers are groping their way through a maze-like cave when they suddenly receive bad news: due to an earthquake nearby, this cave may collapse after $T$ time units. Now they must quickly find a plan that maximizes the number of explorers who can escape within $T$ time units. In one time unit, an explorer can move one cell up, down, left, or right, or stay in place. Unfortunately, although the inside of the cave is spacious, the exits are very narrow: at most one explorer can pass through an exit per time unit.

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.

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 one line containing a single integer, the maximum number of explorers that can escape within $T$ time units.

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