摘要

“轰炸敌人”这道题名字听起来就很带感，它其实是一个二维网格搜索问题。我们要找到一个能放置炸弹的位置，让炸掉的敌人最多。虽然题目看起来复杂，但只要把计算方式优化一下，就能高效解决。今天这篇文章会带大家把题目拆开讲透，写出 Swift 可运行的解法，并结合实际场景，看看类似的思路怎么用在日常开发里。

描述

题目是这样的：

• 给定一个 m x n 的网格。

• 每个格子可能是以下几种情况：

  • 'W'：墙，炸弹的威力不能穿过这里。
  • 'E'：敌人，炸弹能炸到。
  • '0'：空位，可以放炸弹。

• 你的任务是找出一个位置放炸弹，能够炸死的敌人最多，并返回这个最大值。

炸弹的规则很简单：

• 它的威力可以沿着上下左右四个方向延伸。
• 但是，一旦遇到墙 'W' 就会停止。

举个例子：

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

解释：
最佳位置是 grid[1][1]。放在这里能炸到左边和下边的敌人，再加上上方的敌人，总共 3 个。

题解答案

很多人一开始会写一个暴力解：

• 遍历每个 '0'，然后上下左右扫描，看能炸多少敌人。
• 这样做的复杂度是 O(m * n * (m + n))，大输入下会超时。

更聪明的做法是：

• 动态规划（DP）+ 预处理。
• 思路是提前算好每个方向上能炸多少敌人，存下来。这样放炸弹时只需要常数时间就能得到答案。

题解代码分析

下面是 Swift 的完整可运行代码：

import Foundationclass Solution {func maxKilledEnemies(_ grid: [[Character]]) -> Int {guard !grid.isEmpty, !grid[0].isEmpty else { return 0 }let m = grid.count, n = grid[0].count// 用来存储从四个方向能炸到的敌人数var rowHits = Array(repeating: 0, count: n)var result = 0for i in 0..<m {var colHits = 0for j in 0..<n {// 每次遇到行的开头或者墙，重新计算这一行的敌人数if j == 0 || grid[i][j-1] == "W" {colHits = 0var k = jwhile k < n && grid[i][k] != "W" {if grid[i][k] == "E" {colHits += 1}k += 1}}// 每次遇到列的开头或者墙，重新计算这一列的敌人数if i == 0 || grid[i-1][j] == "W" {rowHits[j] = 0var k = iwhile k < m && grid[k][j] != "W" {if grid[k][j] == "E" {rowHits[j] += 1}k += 1}}// 当前位置是空位，才有资格放炸弹if grid[i][j] == "0" {result = max(result, colHits + rowHits[j])}}}return result}
}// Demo 演示
let grid: [[Character]] = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]
]let solution = Solution()
print("输入:")
for row in grid {print(row)
}
print("输出:", solution.maxKilledEnemies(grid))

代码解析

1. colHits：用来记录当前行在连续区间内能炸到的敌人数。
2. rowHits[j]：用来记录当前列在连续区间内能炸到的敌人数。
3. 每次遇到墙 W，重新计算后面的敌人数。
4. 遍历到空位 '0' 时，把行和列的敌人数加起来，就是当前位置能炸到的敌人数。

这样，所有计算都在一次遍历里完成，大大降低了复杂度。

示例测试及结果

运行上面的 Demo，会输出：

输入:
["0", "E", "0", "0"]
["E", "0", "W", "E"]
["0", "E", "0", "0"]
输出: 3

说明我们选的位置 grid[1][1] 确实能炸到最多敌人。

你也可以自己尝试不同的地图，比如：

[["W","E","0","E"],["0","W","E","0"],["E","0","E","W"]]

代码会很快算出最佳位置。

时间复杂度

• 整个网格遍历一遍，每个元素在行和列最多只会被计算一次。
• 时间复杂度是 O(m * n)。
• 相比于暴力解法 O(m * n * (m + n))，优化非常明显。

空间复杂度

• 我们额外用了一个数组 rowHits 来保存列方向的结果。
• 空间复杂度是 O(n)。
• 对于大矩阵来说，内存消耗完全可接受。

总结

这道题的精髓就在于：提前预处理 + 避免重复计算。
一旦你意识到“每一行每一列之间被墙切割成独立区间”，思路就会清晰很多。

在实际场景里，类似的优化思路也很常见：
比如在游戏开发里，你可能需要频繁计算某个范围内的攻击目标。如果每次都全局扫描效率就很低，但只要用缓存和预处理，就能大幅度提升性能。

这就是为什么算法训练题不仅仅是刷题，而是能帮我们建立一套“高效解决问题”的思维方式。