P10865 [HBCPC2024] Genshin Impact Startup Forbidden III

“Blue-edged Shot 被 LeavingZ 禁止玩《原神》。然而，今天 LeavingZ 前往了华中科技大学的网络科学与工程学院，参加2024年中国湖北省国际大学生程序设计竞赛，并收获了金牌。 《原神》中的一个活动多多炸弹大冒险已经开始了。这是一个单人游戏，每局游戏都涉及一个池塘。池塘可以被划分为一个 $n×m$ 的网格，其中第 $i$ 行第 $j$ 列的单元格表示为 $(i,j)$。在这些单元格中，有 $k$ 个单元格包含鱼，你将扮演火花骑士克莱，她用炸药来捕鱼。 如果克莱在 $(a,b)$ 位置投放炸弹，那么所有满足$|x-a|+|y-b|\le 1$的单元格 $(x,y)$ 都将被爆炸覆盖。对于每一个被爆炸覆盖的单元格，克莱都会从其中捕到一条鱼。克莱可以在任何位置投放炸弹。问题是，为了捕到所有的鱼，至少需要多少枚`蹦蹦炸弹`？”

无

无

一种可能的方法是在 $(1,2)$ 位置投放两枚炸弹，再在 $(5,5)$ 位置投放另外两枚炸弹。 可以证明没有比这个答案更小的解。