[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$。