P3508. 战场索敌

解题思路

题意一句话：墙壁 # 把地图分割成若干个由非墙格子（空地 . 和敌人格 E）四连通组成的区域，统计敌人数量少于 K 的区域一共有多少个。

本题属于二维网格（岛屿类型）BFS/DFS 模板题，是经典题型《岛屿的最大面积》的变种：把「统计连通块面积」换成「统计连通块里字符 E 的数量」。

关键点：按「非墙区域」搜索，而不是只搜 E

区域由相邻的 . 和 E 共同组成（E 本质也是空地，只是上面站了敌人）。因此 BFS 的扩展条件是格子不是 `#`。同一区域里两个敌人即使隔着若干空地，也属于同一个区域——如果只沿 E 扩展，会把一个区域里被空地隔开的敌人错拆成多块，得到错误答案。

步骤（对应参考代码）

1. 读入行数 n、列数 m、阈值 k 和网格；建 n×m 的访问标记数组。 2. 双重循环扫描网格：遇到一个非 `#` 且未访问的格子，就从它启动一次 BFS——对应发现了一个新区域。 3. BFS 用队列扩展：出队一个坐标，若该格是 E，当前区域敌人数 curNum 加一；向上下左右四个方向尝试，邻格「不越界 + 非 # + 未访问」才入队，并在入队时立即标记已访问。 4. 一次 BFS 结束即走遍一个完整区域，若 curNum < k，答案 ans 加一。 5. 全图扫描结束，输出 ans。

复杂度

• 时间复杂度：O(n × m)。访问标记保证每个格子至多入队一次，每次出队只检查 4 个方向。
• 空间复杂度：O(n × m)，网格、访问数组与最坏情况下的队列。

坑点提醒

• 入队时就标记已访问（而不是出队时才标记），否则同一格子会被多个方向重复入队，既浪费时间又可能重复计数。
• 统计的是敌人数量严格少于 K 的区域（curNum < k），别写成 <=。
• 一个敌人都没有的区域（curNum = 0）同样满足 0 < k，也计入答案，参考代码即如此处理。