2023-01-17

题目传送门

翻译

难度&重要性(1~10):4

题目来源

AtCoder

题目算法

bfs

解题思路

首先，这道题的问题是从家到鱼市摧毁障碍物的最少次数。我们很容易想到用广搜的方法来做。因为 \(2 \le H,W \le 500\)，数据很小，理论上我们可以对于每个障碍物都进行一次爆破。

虽然爆破的范围是 ￥2 \times 3$，方向不一定，但是我们可以将爆破视作以爆破中心 \(3 \times 3\) 范围进行爆破。

最后使用优先队列，以爆破次数进行排序，直到到达鱼市。

完成状态

已完成