摘要

“轟炸敵人”這道題名字聽起來就很帶感，它其實是一個二維網格搜索問題。我們要找到一個能放置炸彈的位置，讓炸掉的敵人最多。雖然題目看起來復雜，但只要把計算方式優化一下，就能高效解決。今天這篇文章會帶大家把題目拆開講透，寫出 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)。
• 對于大矩陣來說，內存消耗完全可接受。

總結

這道題的精髓就在于：提前預處理 + 避免重復計算。
一旦你意識到“每一行每一列之間被墻切割成獨立區間”，思路就會清晰很多。

在實際場景里，類似的優化思路也很常見：
比如在游戲開發里，你可能需要頻繁計算某個范圍內的攻擊目標。如果每次都全局掃描效率就很低，但只要用緩存和預處理，就能大幅度提升性能。

這就是為什么算法訓練題不僅僅是刷題，而是能幫我們建立一套“高效解決問題”的思維方式。