題目資訊

題目編號: 361
題目連結: Bomb Enemy
主題: Array, Dynamic Programming, Matrix

題目敘述

給定一個 $m \times n$ 矩陣 grid，其中每個單元格要麼是一面牆 ‘W’，要麼是一個敵人 ‘E’，或者是空的 ‘0’，返回你可以用一顆炸彈消滅的最大敵人數。你只能將炸彈放置在空的單元格中。

炸彈會消滅從植入點開始，同一行和同一列上的所有敵人，直到遇到牆為止，因為它太強大而無法被摧毀。

範例 1：

範例 1

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

範例 2：

範例 2

輸入: grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
輸出: 1

約束條件：

$m = \text{grid.length}$
$n = \text{grid}[i].\text{length}$
$1 \leq m, n \leq 500$
$\text{grid}[i][j]$ 要麼是 ‘W’，要麼是 ‘E’，或者是 ‘0’。

直覺

這個問題要求我們確定在矩陣網格的一個特定單元格中放置炸彈可以消滅的最大敵人數量。每個單元格可以包含牆、敵人或者是空的，炸彈只能放置在空的單元格中。炸彈將影響同一行和列中的所有敵人，直到遇到牆為止，牆會阻止其效果。我們的目標是遍歷網格並計算從每個空單元格可以消滅的潛在敵人數量，以優化炸彈的放置位置。

解法

解決這個問題的方法是遍歷網格，計算在空單元格中放置炸彈可以消滅的敵人數量：

網格設置：
- 我們初始化一個與輸入 grid 同大小的矩陣 killCount，用來記錄每個空單元格可以消滅的敵人數量。
水平掃描：
- 對每一行，我們遍歷單元格。使用變數 enemyCount 來累積遇到的敵人數量，直到遇到牆 ‘W’ 或行的末端為止。
- 一旦遇到牆或行的末端，對於該段中遇到的每個空單元格 (‘0’)，我們用累積的 enemyCount 增加它的 killCount。
- 在牆或段落邊界後重置 enemyCount，以便為下一系列單元格重新開始。
垂直掃描：
- 同樣，對於每一列，我們從上到下重複這個過程。
- enemyCount 再次用於計算連續的敵人數量，直到遇到牆或列的末端。
- 對於該段中遇到的每個空單元格，我們將敵人數量添加到其對應的 killCount 值中。
- 在遇到牆或列邊界後重置 enemyCount。
確定最大消滅數量：
- 最後，遍歷 killCount 矩陣以找到最大值。此值代表用一枚炸彈可以消滅的最大敵人數量。

這種雙遍歷方法通過利用問題的約束條件來確保潛在消滅數量的有效計算，允許每個空單元格被分析以找到最佳的炸彈放置位置，而不進行冗餘計算。計算的時間複雜度是 $O(m \times n)$，這在問題的約束內是可行的。

程式碼

C++

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 二維向量用於存儲每個位置能殺死的敵人數量
        vector<vector<int>> killCount(m, vector<int>(n, 0));

        // 遍歷每一行以計算水平攻擊的擊殺數量
        for (int i = 0; i < m; i++) {
            int past = 0;
            int enemyCount = 0;
            
            while (past < n) {
                for (int j = 0; past + j < n + 1; j++) {
                    if (past + j == n || grid[i][past + j] == 'W') {
                        for (int k = past; k < past + j; k++) {
                            if (grid[i][k] == '0') {
                                killCount[i][k] += enemyCount;
                            }
                        }
                        enemyCount = 0;
                        past += j + 1;
                        break;
                    } else if (grid[i][past + j] == 'E') {
                        enemyCount++;
                    }
                }
            }
        }

        // 遍歷每一列以計算垂直攻擊的擊殺數量
        for (int i = 0; i < n; i++) {
            int past = 0;
            int enemyCount = 0;
            
            while (past < m) {
                for (int j = 0; past + j < m + 1; j++) {
                    if (past + j == m || grid[past + j][i] == 'W') {
                        for (int k = past; k < past + j; k++) {
                            if (grid[k][i] == '0') {
                                killCount[k][i] += enemyCount;
                            }
                        }
                        enemyCount = 0;
                        past += j + 1;
                        break;
                    } else if (grid[past + j][i] == 'E') {
                        enemyCount++;
                    }
                }
            }
        }

        // 找出可以用一顆炸彈殺死的最多敵人數量
        int maxKill = killCount[0][0];
        for (const auto& row : killCount) {
            int rowMax = *max_element(row.begin(), row.end());
            maxKill = max(maxKill, rowMax);
        }

        return maxKill;
    }
};

Python

class Solution:
    def maxKilledEnemies(self, grid):
        m = len(grid)
        n = len(grid[0])
        
        # 向量用來儲存每個格子可以殺死的敵人數量
        killCount = [[0] * n for _ in range(m)]
        
        # 遍歷每一行計算水平方向攻擊可以殺死的敵人數量
        for i in range(m):
            past = 0
            enemyCount = 0
            
            while past < n:
                for j in range(n + 1):
                    if past + j == n or grid[i][past + j] == 'W':
                        for k in range(past, past + j):
                            if grid[i][k] == '0':
                                killCount[i][k] += enemyCount
                        enemyCount = 0
                        past += j + 1
                        break
                    elif grid[i][past + j] == 'E':
                        enemyCount += 1

        # 遍歷每一列計算垂直方向攻擊可以殺死的敵人數量
        for i in range(n):
            past = 0
            enemyCount = 0
            
            while past < m:
                for j in range(m + 1):
                    if past + j == m or grid[past + j][i] == 'W':
                        for k in range(past, past + j):
                            if grid[k][i] == '0':
                                killCount[k][i] += enemyCount
                        enemyCount = 0
                        past += j + 1
                        break
                    elif grid[past + j][i] == 'E':
                        enemyCount += 1

        # 找出使用一顆炸彈可以殺死的最大敵人數量
        maxKill = killCount[0][0]
        for row in killCount:
            rowMax = max(row)
            maxKill = max(maxKill, rowMax)

        return maxKill

複雜度分析

時間複雜度: $O(m \times n)$
演算法涉及對矩陣的兩次主要遍歷。對於橫向攻擊計算，矩陣中的每一行都需遍歷，時間複雜度為 $O(n)$，其中 $n$ 是列數。由於有 $m$ 行，該部分的演算法複雜度為 $O(m \times n)$。同樣地，對於縱向攻擊計算，每一列需遍歷，時間複雜度為 $O(m)$，由於有 $n$ 列，這部分演算法的複雜度同樣為 $O(m \times n)$。最後，尋找一枚炸彈可以殺死的最大敵人數量涉及行遍歷，時間複雜度為 $O(m \times n)$。因此，演算法的總時間複雜度為 $O(m \times n)$。
空間複雜度: $O(m \times n)$
空間複雜度由 killCount 向量決定，該向量存儲了每個空單元格能夠消滅的敵人數量。此向量的維度為 $m \times n$，與輸入網格大小一致。因此，演算法的空間複雜度為 $O(m \times n)$。

CS Note
En

Leetcode 361. Bomb Enemy

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析