AlgoNote 算法通关：LeetCode 0361「轰炸敌人」双方向预处理动态规划题解

• 教程
• 文档
• 知识库

导读

本篇题解来自 AlgoNote 算法通关手册 的 LeetCode 题解体系，对应题目0361. 轰炸敌人。该题以「矩阵 + 墙体阻挡」为背景，考察如何用**动态规划预处理（分方向累计击杀数）**在 $O(m \times n)$ 时间内求出一颗炸弹能击杀的最大敌人数。读完本文，你将掌握：四方向累计计数的预处理思路、墙体重置计数的边界处理技巧、以及如何将二维矩阵问题拆解为「行方向 + 列方向」两个独立子问题，并把复杂度从暴力枚举的 $O(m^2 \times n^2)$ 降到 $O(m \times n)$。

题目分析

题目描述

给定一个大小为 $m \times n$ 的矩阵grid，其中每个单元格放置一个字符：

• 'W'表示一堵墙（墙体会阻挡炸弹威力）；
• 'E'表示一个敌人；
• '0'（数字 $0$）表示一个空位。

要求：返回使用一颗炸弹可以击杀的最大敌人数目。

限制与说明：

• 炸弹只能放在空位（'0'）中，不能放在墙或敌人所在格；
• 炸弹威力无法穿透墙体，因此只能击杀同一行和同一列、且没有被墙挡住的敌人；
• $m == grid.length$，$n == grid[i].length$；
• $1 \le m, n \le 500$；
• grid[i][j]取值只能是'W'、'E'或'0'。

示例与边界场景

示例 1（墙在中间，上下左右四个方向均有敌人可见）：

输入：grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]] 输出：3

示例 2（墙体整列分隔，炸弹只能击杀未被墙阻挡的敌人）：

输入：grid = [["W","W","W"],["0","0","0"],["E","E","E"]] 输出：1

示例 2 很好地展示了墙体阻挡的语义：炸弹放在第二行任意空位时，水平方向两侧都被墙封死，垂直方向虽然整列都是敌人，但一行内任意空位向同一列的上下看只能看到一侧的敌人（例如放在[1][0]只能击杀[2][0]这一个敌人），因此答案是 $1$。

解题思路：动态规划 + 四方向预处理

为什么不能用朴素枚举

最直观的做法是：枚举每个空位，再向上下左右四个方向逐个扫描敌人，遇到墙就停止。对于 $m \times n$ 个空位，每个空位最坏需要扫描 $O(m + n)$ 个格子，总时间复杂度为 $O(m \times n \times (m + n))$；在最坏 $500 \times 500$ 的矩阵下会退化到约 $O(m^2 \times n^2)$ 量级，明显不可取。

核心思想：分方向累计计数

炸弹能击杀的敌人数量，本质上是「同一行左右两侧被墙截断区间内的敌人」与「同一列上下两侧被墙截断区间内的敌人」之和。因此可以把问题拆成两个独立的子问题：

1. 行方向：对每一行，分别从左到右、从右到左扫描，累计「从最近一面墙到当前位置之间」的敌人数；
2. 列方向：对每一列，分别从上到下、从下到上扫描，累计「从最近一面墙到当前位置之间」的敌人数。

由于墙体会中断威力，扫描时只要遇到'W'就把计数器清零，重新开始累计；遇到'E'则计数器加一；遇到空位'0'，就把当前计数器累加到该位置的预处理结果中。

算法步骤

1. 预处理行方向：用二维数组row_kills记录每个位置在行方向上能击杀的敌人数。
   • 从左到右扫描每一行，把「左侧最近墙到当前位置之间」的敌人数累加到row_kills[i][j]；
   • 再从右到左扫描每一行，把「右侧最近墙到当前位置之间」的敌人数继续累加到row_kills[i][j]，两次结果合并即为该位置水平方向的总击杀数。
2. 预处理列方向：用二维数组col_kills记录每个位置在列方向上能击杀的敌人数，扫描方向为从上到下、从下到上，逻辑与行方向完全对称。
3. 计算最大值：遍历矩阵中所有空位'0'，令total_kills = row_kills[i][j] + col_kills[i][j]，更新max_kills = max(max_kills, total_kills)。

这里的关键变量定义如下：

• $m$：矩阵行数；$n$：矩阵列数；
• $row_kills[i][j]$：位置 $(i, j)$ 在行方向上（左右两侧、墙内）能击杀的敌人数；
• $col_kills[i][j]$：位置 $(i, j)$ 在列方向上（上下两侧、墙内）能击杀的敌人数；
• $max_kills$：最终能击杀的最大敌人数。

参考代码

class Solution: def maxKilledEnemies(self, grid: List[List[str]]) -> int: if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) max_kills = 0 # 预处理：计算每个位置在行方向上能击杀的敌人数 row_kills = [[0] * n for _ in range(m)] # 从左到右计算行方向的击杀数 for i in range(m): count = 0 for j in range(n): if grid[i][j] == 'W': count = 0 # 遇到墙，重置计数 elif grid[i][j] == 'E': count += 1 # 遇到敌人，增加计数 else: # 空位 row_kills[i][j] += count # 从右到左计算行方向的击杀数 for i in range(m): count = 0 for j in range(n - 1, -1, -1): if grid[i][j] == 'W': count = 0 # 遇到墙，重置计数 elif grid[i][j] == 'E': count += 1 # 遇到敌人，增加计数 else: # 空位 row_kills[i][j] += count # 预处理：计算每个位置在列方向上能击杀的敌人数 col_kills = [[0] * n for _ in range(m)] # 从上到下计算列方向的击杀数 for j in range(n): count = 0 for i in range(m): if grid[i][j] == 'W': count = 0 # 遇到墙，重置计数 elif grid[i][j] == 'E': count += 1 # 遇到敌人，增加计数 else: # 空位 col_kills[i][j] += count # 从下到上计算列方向的击杀数 for j in range(n): count = 0 for i in range(m - 1, -1, -1): if grid[i][j] == 'W': count = 0 # 遇到墙，重置计数 elif grid[i][j] == 'E': count += 1 # 遇到敌人，增加计数 else: # 空位 col_kills[i][j] += count # 计算每个空位能击杀的敌人数，并更新最大值 for i in range(m): for j in range(n): if grid[i][j] == '0': # 空位 total_kills = row_kills[i][j] + col_kills[i][j] max_kills = max(max_kills, total_kills) return max_kills

复杂度分析

• 时间复杂度：$O(m \times n)$。矩阵被完整遍历四次（行方向从左到右、从右到左各一次，列方向从上到下、从下到上各一次），每次遍历都是 $O(m \times n)$，最后求最大值再遍历一次，仍为 $O(m \times n)$。
• 空间复杂度：$O(m \times n)$。需要row_kills与col_kills两个 $m \times n$ 的二维数组存储预处理结果。

实现细节与易错点

1. 空矩阵特判：if not grid or not grid[0]: return 0必须在所有遍历之前完成，避免grid[0]越界。
2. 计数器的语义：count表示「从最近一面墙（或矩阵边界）到当前扫描位置之间」出现的敌人数量。遇到'W'清零是因为墙体切断了炸弹威力，墙两侧的敌人互不可见。
3. 空位才累加结果：行/列预处理只在遇到空位'0'时把count写入row_kills/col_kills，因为炸弹只能放置在空位；敌人格和墙体格本身不参与最终最大值统计。
4. 最终统计只看空位：最后的max_kills更新循环用if grid[i][j] == '0'过滤，保证炸弹一定放在空位上，与题目要求严格一致。
5. 左右/上下扫描的对称性：两次反向扫描解决的是「行方向左右两侧」与「列方向上下两侧」的累计问题，缺一不可；只做单方向扫描会漏掉一半的敌人。

思路延伸：与仓库同类题解的关系

本题属于「数组、动态规划、矩阵」标签下的经典中等题，在 AlgoNote 题解列表 中位于 0300-0399 区间。它体现的「分方向累计 + 墙体重置」预处理模式，与仓库中其他矩阵类动态规划题解一脉相承：

• 0542. 01 矩阵：同样是 $m \times n$ 矩阵上的距离类问题，展示了「暴力逐点搜索代价过高 → 换一种累计/递推方式把总复杂度降到 $O(m \times n)$」的相同思维路径；
• 0363. 矩形区域不超过 K 的最大数值和、0304. 二维区域和检索：同属二维矩阵预处理家族，核心都是「提前算好中间量，查询时 O(1) 合并」；
• 动态规划基础理论：仓库在 08 章 系统讲解了动态规划的最优子结构、重叠子问题、无后效性三大特征，本题的预处理表正是「表格处理方法」的典型应用——每个位置的累计值一旦算定就固定不变，满足无后效性，后续合并查询时直接取用。

如果你正在系统刷「数组 / 矩阵 / 动态规划」类题目，可以按 分类题单 依次练习，把本题与上述题解对照学习，理解「预处理换时间」这一通用优化套路。

总结

0361. 轰炸敌人是一道考察「矩阵方向累计 + 墙体边界处理」的动态规划预处理题。核心结论如下：

1. 把「四方向击杀总数」拆分为「行方向（左 + 右）」与「列方向（上 + 下）」两个独立子问题，各自用一遍正向扫描 + 一遍反向扫描完成累计；
2. 遇到'W'清零计数器、遇到'E'累加、遇到'0'记录结果，是本题最关键的边界处理模式；
3. 最终只统计空位上的row_kills + col_kills，取最大值即答案；
4. 时间复杂度 $O(m \times n)$、空间复杂度 $O(m \times n)$，在 $m, n \le 500$ 的约束下可以轻松通过。

掌握本题后，建议继续阅读仓库中 同区间的矩阵/DP 题解 与 动态规划章节，把「分方向累计」「墙体重置」「预处理表」这些技巧迁移到更多二维矩阵问题上。

• 教程
• 文档
• 知识库