#P14065. [PO Final 2022] 对弈 / Laserschack
[PO Final 2022] 对弈 / Laserschack
题目描述
Fredrik 和 Abdullah 正在对弈。棋局在一个网格上进行,目标是用激光射中对方的国王。Abdullah 有一枚攻击棋子,按下按钮后会向四个方向(上、下、左、右)同时发射激光,在网格中记作 A
。Fredrik 的国王记作 K
。网格中还有镜子棋子,记作 o
。当激光击中一枚镜子棋子时,光束会从该格子向四个方向同时继续传播。
此时局面情况如下:只要 Abdullah 按下按钮发射激光,他就会获胜。为了阻止 Abdullah 取胜,Fredrik 在棋盘上投放了烟雾弹,记作 R
。烟雾会阻止激光穿过所在格子。每过 1 秒,烟雾会向四个相邻的格子扩散。如果攻击棋子或国王处在烟雾中,则 Abdullah 无法获胜。
问:还需要多少秒 Abdullah 才无法再通过按下按钮立即取胜?换言之,还需要多少秒,烟雾的扩散会使得从攻击棋子发出的激光不再能够到达国王?保证初始时,激光可以不经过任何烟雾,从攻击棋子到达国王。
输入格式
第一行包含两个整数 和 (),表示构成棋盘的网格的行数和列数。
接下来的 行描述棋盘的布局。第 行包含 个字符,表示第 行的内容。每个字符为下列之一:
.
表示空格;o
表示镜子棋子;R
表示一枚烟雾弹;A
表示攻击棋子;K
表示国王。
保证 A
和 K
各恰好出现一次,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 秒时,每个样例中烟雾的扩散情况。
子任务
本题采用捆绑测试。
| 子任务编号 | 得分 | 限制 |
|:-:|:-:|---|
| | | |
| | | 棋盘上恰好有一个 R
。 |
| | | 没有空格(.
)。 |
| | | |
| | | 无其他限制。 |