尧图网站建设 
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本篇题解来自 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)$ 量级明显不可取。核心思想分方向累计计数炸弹能击杀的敌人数量本质上是「同一行左右两侧被墙截断区间内的敌人」与「同一列上下两侧被墙截断区间内的敌人」之和。因此可以把问题拆成两个独立的子问题行方向对每一行分别从左到右、从右到左扫描累计「从最近一面墙到当前位置之间」的敌人数列方向对每一列分别从上到下、从下到上扫描累计「从最近一面墙到当前位置之间」的敌人数。由于墙体会中断威力扫描时只要遇到W就把计数器清零重新开始累计遇到E则计数器加一遇到空位0就把当前计数器累加到该位置的预处理结果中。算法步骤预处理行方向用二维数组row_kills记录每个位置在行方向上能击杀的敌人数。从左到右扫描每一行把「左侧最近墙到当前位置之间」的敌人数累加到row_kills[i][j]再从右到左扫描每一行把「右侧最近墙到当前位置之间」的敌人数继续累加到row_kills[i][j]两次结果合并即为该位置水平方向的总击杀数。预处理列方向用二维数组col_kills记录每个位置在列方向上能击杀的敌人数扫描方向为从上到下、从下到上逻辑与行方向完全对称。计算最大值遍历矩阵中所有空位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$ 的二维数组存储预处理结果。实现细节与易错点空矩阵特判if not grid or not grid[0]: return 0必须在所有遍历之前完成避免grid[0]越界。计数器的语义count表示「从最近一面墙或矩阵边界到当前扫描位置之间」出现的敌人数量。遇到W清零是因为墙体切断了炸弹威力墙两侧的敌人互不可见。空位才累加结果行/列预处理只在遇到空位0时把count写入row_kills/col_kills因为炸弹只能放置在空位敌人格和墙体格本身不参与最终最大值统计。最终统计只看空位最后的max_kills更新循环用if grid[i][j] 0过滤保证炸弹一定放在空位上与题目要求严格一致。左右/上下扫描的对称性两次反向扫描解决的是「行方向左右两侧」与「列方向上下两侧」的累计问题缺一不可只做单方向扫描会漏掉一半的敌人。思路延伸与仓库同类题解的关系本题属于「数组、动态规划、矩阵」标签下的经典中等题在 AlgoNote 题解列表 中位于 0300-0399 区间。它体现的「分方向累计 墙体重置」预处理模式与仓库中其他矩阵类动态规划题解一脉相承0542. 01 矩阵同样是 $m \times n$ 矩阵上的距离类问题展示了「暴力逐点搜索代价过高 → 换一种累计/递推方式把总复杂度降到 $O(m \times n)$」的相同思维路径0363. 矩形区域不超过 K 的最大数值和、0304. 二维区域和检索同属二维矩阵预处理家族核心都是「提前算好中间量查询时 O(1) 合并」动态规划基础理论仓库在 08 章 系统讲解了动态规划的最优子结构、重叠子问题、无后效性三大特征本题的预处理表正是「表格处理方法」的典型应用——每个位置的累计值一旦算定就固定不变满足无后效性后续合并查询时直接取用。如果你正在系统刷「数组 / 矩阵 / 动态规划」类题目可以按 分类题单 依次练习把本题与上述题解对照学习理解「预处理换时间」这一通用优化套路。总结0361. 轰炸敌人是一道考察「矩阵方向累计 墙体边界处理」的动态规划预处理题。核心结论如下把「四方向击杀总数」拆分为「行方向左 右」与「列方向上 下」两个独立子问题各自用一遍正向扫描 一遍反向扫描完成累计遇到W清零计数器、遇到E累加、遇到0记录结果是本题最关键的边界处理模式最终只统计空位上的row_kills col_kills取最大值即答案时间复杂度 $O(m \times n)$、空间复杂度 $O(m \times n)$在 $m, n \le 500$ 的约束下可以轻松通过。掌握本题后建议继续阅读仓库中 同区间的矩阵/DP 题解 与 动态规划章节把「分方向累计」「墙体重置」「预处理表」这些技巧迁移到更多二维矩阵问题上。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote「算法通关手册」LeetCode 0072 编辑距离Levenshtein Distance双串动态规划全解AlgoNote「算法通关手册」LeetCode 0072 编辑距离Levenshtein Distance双串动态规划全解 本篇题解基于开源仓库 Alg教程文档知识库AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划 导读 本篇是 AlgoNote算法通关手册中 009教程文档知识库3分钟写出化学方程式yn Markdown编辑器的LaTeX公式指南3分钟写出化学方程式yn Markdown编辑器的LaTeX公式指南 要在Word里排一个带上下标的化学方程式往往得插公式对象、调箭头位置最后间距还是歪的教程文档知识库上一篇MAA跨平台部署终极指南Windows/Linux/macాలుOS全平台RR实战下一篇Midway 集成 Leoric ORM 组件从配置到源码级的数据源管理实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 AlgoNote 算法通关：LeetCode 0361「轰炸敌人」双方向预处理动态规划题解
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本篇题解来自 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)$ 量级明显不可取。核心思想分方向累计计数炸弹能击杀的敌人数量本质上是「同一行左右两侧被墙截断区间内的敌人」与「同一列上下两侧被墙截断区间内的敌人」之和。因此可以把问题拆成两个独立的子问题行方向对每一行分别从左到右、从右到左扫描累计「从最近一面墙到当前位置之间」的敌人数列方向对每一列分别从上到下、从下到上扫描累计「从最近一面墙到当前位置之间」的敌人数。由于墙体会中断威力扫描时只要遇到W就把计数器清零重新开始累计遇到E则计数器加一遇到空位0就把当前计数器累加到该位置的预处理结果中。算法步骤预处理行方向用二维数组row_kills记录每个位置在行方向上能击杀的敌人数。从左到右扫描每一行把「左侧最近墙到当前位置之间」的敌人数累加到row_kills[i][j]再从右到左扫描每一行把「右侧最近墙到当前位置之间」的敌人数继续累加到row_kills[i][j]两次结果合并即为该位置水平方向的总击杀数。预处理列方向用二维数组col_kills记录每个位置在列方向上能击杀的敌人数扫描方向为从上到下、从下到上逻辑与行方向完全对称。计算最大值遍历矩阵中所有空位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$ 的二维数组存储预处理结果。实现细节与易错点空矩阵特判if not grid or not grid[0]: return 0必须在所有遍历之前完成避免grid[0]越界。计数器的语义count表示「从最近一面墙或矩阵边界到当前扫描位置之间」出现的敌人数量。遇到W清零是因为墙体切断了炸弹威力墙两侧的敌人互不可见。空位才累加结果行/列预处理只在遇到空位0时把count写入row_kills/col_kills因为炸弹只能放置在空位敌人格和墙体格本身不参与最终最大值统计。最终统计只看空位最后的max_kills更新循环用if grid[i][j] 0过滤保证炸弹一定放在空位上与题目要求严格一致。左右/上下扫描的对称性两次反向扫描解决的是「行方向左右两侧」与「列方向上下两侧」的累计问题缺一不可只做单方向扫描会漏掉一半的敌人。思路延伸与仓库同类题解的关系本题属于「数组、动态规划、矩阵」标签下的经典中等题在 AlgoNote 题解列表 中位于 0300-0399 区间。它体现的「分方向累计 墙体重置」预处理模式与仓库中其他矩阵类动态规划题解一脉相承0542. 01 矩阵同样是 $m \times n$ 矩阵上的距离类问题展示了「暴力逐点搜索代价过高 → 换一种累计/递推方式把总复杂度降到 $O(m \times n)$」的相同思维路径0363. 矩形区域不超过 K 的最大数值和、0304. 二维区域和检索同属二维矩阵预处理家族核心都是「提前算好中间量查询时 O(1) 合并」动态规划基础理论仓库在 08 章 系统讲解了动态规划的最优子结构、重叠子问题、无后效性三大特征本题的预处理表正是「表格处理方法」的典型应用——每个位置的累计值一旦算定就固定不变满足无后效性后续合并查询时直接取用。如果你正在系统刷「数组 / 矩阵 / 动态规划」类题目可以按 分类题单 依次练习把本题与上述题解对照学习理解「预处理换时间」这一通用优化套路。总结0361. 轰炸敌人是一道考察「矩阵方向累计 墙体边界处理」的动态规划预处理题。核心结论如下把「四方向击杀总数」拆分为「行方向左 右」与「列方向上 下」两个独立子问题各自用一遍正向扫描 一遍反向扫描完成累计遇到W清零计数器、遇到E累加、遇到0记录结果是本题最关键的边界处理模式最终只统计空位上的row_kills col_kills取最大值即答案时间复杂度 $O(m \times n)$、空间复杂度 $O(m \times n)$在 $m, n \le 500$ 的约束下可以轻松通过。掌握本题后建议继续阅读仓库中 同区间的矩阵/DP 题解 与 动态规划章节把「分方向累计」「墙体重置」「预处理表」这些技巧迁移到更多二维矩阵问题上。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote「算法通关手册」LeetCode 0072 编辑距离Levenshtein Distance双串动态规划全解AlgoNote「算法通关手册」LeetCode 0072 编辑距离Levenshtein Distance双串动态规划全解 本篇题解基于开源仓库 Alg教程文档知识库AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划 导读 本篇是 AlgoNote算法通关手册中 009教程文档知识库3分钟写出化学方程式yn Markdown编辑器的LaTeX公式指南3分钟写出化学方程式yn Markdown编辑器的LaTeX公式指南 要在Word里排一个带上下标的化学方程式往往得插公式对象、调箭头位置最后间距还是歪的教程文档知识库上一篇MAA跨平台部署终极指南Windows/Linux/macాలుOS全平台RR实战下一篇Midway 集成 Leoric ORM 组件从配置到源码级的数据源管理实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考