P14065 [PO Final 2022] 对弈 / Laserschack

Fredrik 和 Abdullah 正在对弈。棋局在一个网格上进行，目标是用激光射中对方的国王。Abdullah 有一枚攻击棋子，按下按钮后会向四个方向（上、下、左、右）同时发射激光，在网格中记作 `A`。Fredrik 的国王记作 `K`。网格中还有镜子棋子，记作 `o`。当激光击中一枚镜子棋子时，光束会从该格子向四个方向同时继续传播。 此时局面情况如下：只要 Abdullah 按下按钮发射激光，他就会获胜。为了阻止 Abdullah 取胜，Fredrik 在棋盘上投放了烟雾弹，记作 `R`。烟雾会阻止激光穿过所在格子。每过 1 秒，烟雾会向四个相邻的格子扩散。如果攻击棋子或国王处在烟雾中，则 Abdullah 无法获胜。 问：还需要多少秒 Abdullah 才无法再通过按下按钮立即取胜？换言之，还需要多少秒，烟雾的扩散会使得从攻击棋子发出的激光不再能够到达国王？保证初始时，激光可以不经过任何烟雾，从攻击棋子到达国王。

第一行包含两个整数 $ R $ 和 $ C $（$ 1 \le R,\ 1 \le C,\ R \times C \le 40000 $），表示构成棋盘的网格的行数和列数。 接下来的 $ R $ 行描述棋盘的布局。第 $ i $ 行包含 $ C $ 个字符，表示第 $ i $ 行的内容。每个字符为下列之一： - `.` 表示空格； - `o` 表示镜子棋子； - `R` 表示一枚烟雾弹； - `A` 表示攻击棋子； - `K` 表示国王。 保证 `A` 和 `K` 各恰好出现一次，`R` 至少出现一次，且起始时从攻击棋子发出的激光能到达国王。

输出一个正整数——直到激光不再能到达国王所需的秒数。

### 样例解释  图 1：样例 1 在 1 秒后。  图 2：样例 2 在 3 秒后。  图 3：样例 3 在 2 秒后。 以上各图展示了在激光仍能到达国王的最后 1 秒时，每个样例中烟雾的扩散情况。 ### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $10$ | $ R = 1 $ | | $2$ | $20$ | 棋盘上恰好有一个 `R`。 | | $3$ | $20$ | 没有空格（`.`）。 | | $4$ | $20$ | $ R \times C \le 400 $ | | $5$ | $30$ | 无其他限制。 |