T3 最远哨点（supply）

题目描述

某哨所需要在一片 $r$ 行 $c$ 列的网格地上布置哨兵。网格的每个格子只有三种状态：

• #：障碍，不可通过；
• P：已经部署的哨兵；
• .：空地，可以再选择一个作为新哨点。

哨兵只能沿上下左右四个方向相邻移动。对于每一块空地，它到最近哨兵的距离，等于从这块空地出发，沿四方向走到任意一个 P 格子所需的最少步数。

现在要选择一块空地作为新哨点，使得它到最近哨兵的距离尽可能大。请你求出这个最大距离。如果没有任何一块空地能够到达哨兵，则输出 $-1$。

输入文件为 supply.in，输出文件为 supply.out。

输入格式

第一行两个正整数 $r,c$，表示网格的行数与列数。

接下来 $r$ 行，每行一个长度为 $c$ 的字符串，描述网格。

输出格式

一行一个整数，表示答案。

样例 1 输入

3 3
P..
.#.
..P

样例 1 输出

2

样例 1 解释

哨兵位于左上角与右下角。空地 $(1,3)$ 与 $(3,1)$ 到最近哨兵的距离都是 $2$，这是所有空地中最大的；障碍 $(2,2)$ 不参与计算。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $r,c \le 20$。
• 对于 $100\%$ 的数据，保证 $1 \le r,c \le 1000$，网格中至少有一个 P。