#P14065. [PO Final 2022] 对弈 / Laserschack

[PO Final 2022] 对弈 / Laserschack

题目描述

Fredrik 和 Abdullah 正在对弈。棋局在一个网格上进行,目标是用激光射中对方的国王。Abdullah 有一枚攻击棋子,按下按钮后会向四个方向(上、下、左、右)同时发射激光,在网格中记作 A。Fredrik 的国王记作 K。网格中还有镜子棋子,记作 o。当激光击中一枚镜子棋子时,光束会从该格子向四个方向同时继续传播。

此时局面情况如下:只要 Abdullah 按下按钮发射激光,他就会获胜。为了阻止 Abdullah 取胜,Fredrik 在棋盘上投放了烟雾弹,记作 R。烟雾会阻止激光穿过所在格子。每过 1 秒,烟雾会向四个相邻的格子扩散。如果攻击棋子或国王处在烟雾中,则 Abdullah 无法获胜。

问:还需要多少秒 Abdullah 才无法再通过按下按钮立即取胜?换言之,还需要多少秒,烟雾的扩散会使得从攻击棋子发出的激光不再能够到达国王?保证初始时,激光可以不经过任何烟雾,从攻击棋子到达国王。

输入格式

第一行包含两个整数 R R C C 1R, 1C, R×C40000 1 \le R,\ 1 \le C,\ R \times C \le 40000 ),表示构成棋盘的网格的行数和列数。

接下来的 R R 行描述棋盘的布局。第 i i 行包含 C C 个字符,表示第 i i 行的内容。每个字符为下列之一:

  • . 表示空格;
  • o 表示镜子棋子;
  • R 表示一枚烟雾弹;
  • A 表示攻击棋子;
  • K 表示国王。

保证 AK 各恰好出现一次,R 至少出现一次,且起始时从攻击棋子发出的激光能到达国王。

输出格式

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

3 3
.Ao
R..
.Ko

2
5 8
A......o
..K.o...
o....o.o
..o..o..
R...o..o

4
10 9
oo.o.oRR.
.K.oo..R.
....oo..R
..R......
..R......
A....o.o.
...R.....
.....o.o.
.........
o....o..R

3

提示

样例解释

图 1:样例 1 在 1 秒后。

图 2:样例 2 在 3 秒后。

图 3:样例 3 在 2 秒后。

以上各图展示了在激光仍能到达国王的最后 1 秒时,每个样例中烟雾的扩散情况。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | 11 | 1010 | R=1 R = 1 | | 22 | 2020 | 棋盘上恰好有一个 R。 | | 33 | 2020 | 没有空格(.)。 | | 44 | 2020 | R×C400 R \times C \le 400 | | 55 | 3030 | 无其他限制。 |