1997: 脱险
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：5
题目描述
一批探险队员正在一个迷宫一样的山洞里摸索，突然他们得到了一个糟糕的消息，由于附近发生地震，这个山洞将有可能在T个单位时间后坍塌。现在他们要用最快的速度找出一个方案，使得在T个单位时间内逃出的队员最多。已知探险队员在一个单位时间内可以向前后左右任一方向移动一格，也可以停留在原地不动。有一个糟糕的情况是，虽然山洞的内部比较宽敞，但山洞的出口都非常狭窄，一个单位时间只能允许一名队员通过。
山洞的地图用一个R*C的字符矩阵表示，其中'.'表示在开始的时候没有探险队员的空地，空地可以容纳任意多的探险队员；'P'表示在开始的时候有探险队员的空地，我们假设在开始的时候所有的队员都在不同的位置上，且没有队员恰好位于出口所在的方格；'*'表示障碍物，探险队员不能经过被障碍物占据的方格；'O'(大写字母O)表示出口，输入数据保证出口一定位于地图的边界上，即只有第1行,第R行,第1列,第C列有可能出现'O'。另外，输入数据保证整个地图被边界和出口围住，即第1行,第R行,第1列,第C列只能是'*'或'O'.
输入
输入文件的第一行是用空格隔开的两个整数R和C，表示地图的大小。第二行是整数T，即山洞将要坍塌的时间。接下来R行，每行包含C个字符，表示一幅山洞地图。
输出
输出一行，包含一个整数，即T个单位时间内最多能逃出的人数。
样例输入 复制
5 5
4
*****
*P..*
O**.O
*P..*
*****
样例输出 复制
1提示
【样例说明】
山洞有两个出口，但只有右边的出口是可以到达的。虽然在3个单位时间内两人都可以到达出口左侧的方格处，但由于在出口处一个单位时间只能允许一人通过，故4个单位时间内只能逃出一人。两人都逃出需要5个单位时间。
【数据规模与约定】
对于30%的数据，队员数和出口数均不超过10
对于100%的数据，3 ≤ R, C ≤ 12，0 ＜ T ≤ 50