题解：AT_abc370_d [ABC370D] Cross Explosion

天使宝贝 · 2024-09-08 08:49:39 · 题解

题面传送门

吐槽：为啥很多大佬说 D 卡常，但是蒟蒻觉得不卡啊。

题目大意

给你一个 H \times W 的网格，初始网格上全是墙壁。 现有 q 次操作，对于每次操作，给你两个整数 R_q 和 C_q，然后会发生以下过程：

• 如果在 (R_q, C_q) 处有墙，则摧毁该面墙，并结束本次操作。
• 如果在 (R_q, C_q) 处没有墙，则摧毁在该位置上下左右出现的第一面墙。

请你输出这 q 次操作后剩余墙的数量。

思路&分析

不妨先想想暴力，暴力很简单，只需要判断一下当前位置是否有墙，如果有就摧毁这面墙，否则就朝上下左右四个方向遍历，找到第一面墙摧毁即可。

考虑优化，我们可以开一个数组来记录这个点被重复炸了几次，记为 v_{i, j}，然后对于每次操作，我们只需要从 x + v_{i, j}，x - v_{i, j}，y + v_{i, j}，y - v_{i, j} 开始找寻第一次出现的墙即可。

于是我们就愉快的解决了此题。

CODE

赛时代码