[TJOI2007] 脱险

题目背景

一批探险队员正在一个迷宫一样的山洞里摸索,突然他们得到了一个糟糕的消息,由于附近发生地震,这个山洞将有可能在 $T$ 个单位时间后坍塌。现在他们要用最快的速度找出一个方案,使得在 $T$ 个单位时间内逃出的队员最多。已知探险队员在一个单位时间内可以向前后左右任一方向移动一格,也可以停留在原地不动。有一个糟糕的情况是,虽然山洞的内部比较宽敞,但山洞的出口都非常狭窄,一个单位时间只能允许一名队员通过。

题目描述

山洞的地图用一个 $R \times C$ 的字符矩阵表示: - `.` 表示在开始的时候没有探险队员的空地,空地可以容纳任意多的探险队员; - `P`表示在开始的时候有探险队员的空地,我们假设在开始的时候所有的队员都在不同的位置上,且没有队员恰好位于出口所在的方格; - `*` 表示障碍物,探险队员不能经过被障碍物占据的方格; - `O`(大写字母 `O`)表示出口,输入数据保证出口一定位于地图的边界上,即只有第 $1$ 行,第 $R$ 行,第 $1$ 列,第 $C$ 列有可能出现 `O`。 另外,输入数据保证整个地图被边界和出口围住,即第 $1$ 行,第 $R$ 行,第 $1$ 列,第 $C$ 列只能是 `*` 或 `O`。

输入输出格式

输入格式


输入文件的第一行是用空格隔开的两个整数 $R$ 和 $C$,表示地图的大小。第二行是整数 $T$,即山洞将要坍塌的时间。接下来 $R$ 行,每行包含 $C$ 个字符,表示一幅山洞地图。

输出格式


输出一行,包含一个整数,即 $T$ 个单位时间内最多能逃出的人数。

输入输出样例

输入样例 #1

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

输出样例 #1

1

说明

山洞有两个出口,但只有右边的出口是可以到达的。虽然在 $3$ 个单位时间内两人都可以到达出口左侧的方格处,但由于在出口处一个单位时间只能允许一人通过,故 $4$ 个单位时间内只能逃出一人。两人都逃出需要 $5$ 个单位时间。 - 对于 $30\%$ 的数据,队员数和出口数均不超过 $10$; - 对于 $100\%$ 的数据,$3 \le R, C \le 12,0 < T \le 50$。