361. Bomb Enemy

Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed. Note: You can only put the bomb at an empty cell.

Example:

Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3 
Explanation: For the given grid,

0 E 0 0 
E 0 W E 
0 E 0 0

Placing a bomb at (1,1) kills 3 enemies.

dp[i][j]代表把炸彈放在(i, j)能炸死的最多敵人數量。每個loop內都有一個local variable, cnt紀錄當時掃描能被炸死的敵人數量。

// Naive 2D DP
int maxKilledEnemies(vector<vector<char>>& grid) { // time: O(m * n); space: O(m * n)
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<vector<int> > dp(m, vector<int>(n, 0));
    // traverse each row twice, from left and from right
    for (int i = 0; i < m; ++i) {
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 'W') cnt = 0;
            else if (grid[i][j] == 'E') ++cnt;
            else dp[i][j] += cnt;
        }
        cnt = 0; // reset
        for (int j = n - 1; j >= 0; --j) {
            if (grid[i][j] == 'W') cnt = 0;
            else if (grid[i][j] == 'E') ++cnt;
            else dp[i][j] += cnt;
        }
    }
    int res = 0;
    // traverse each column twice, from top and from bottom
    for (int j = 0; j < n; ++j) {
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            if (grid[i][j] == 'W') cnt = 0;
            else if (grid[i][j] == 'E') ++cnt;
            else dp[i][j] += cnt;
        }
        cnt = 0; // reset
        for (int i = m - 1; i >= 0; --i) {
            if (grid[i][j] == 'W') cnt = 0;
            else if (grid[i][j] == 'E') ++cnt;
            else {
                dp[i][j] += cnt;
                res = max(res, dp[i][j]);
            }
        }
    }
    return res;
}

由於掃描方式是從上到下一列一列掃描，每一列再掃描每一行，所以我們在掃描某一列時，我們只需要一個變數來記錄當前這個row上能被炸死的敵人數量。掃描每一行時，利用一個1D vector紀錄該column能被炸死的敵人數量並重複使用直到遇到牆壁再重新計算。

// Space-Optimized 1D DP
int maxKilledEnemies(vector<vector<char>>& grid) { // time: O(m * n); space: O(n)
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size(), rowCnt = 0, res = 0;
    vector<int> colCnt(n, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j == 0 || grid[i][j - 1] == 'W') {
                rowCnt = 0;
                for (int k = j; k < n && grid[i][k] != 'W'; ++k) {
                    rowCnt += (grid[i][k] == 'E');
                }
            }
            if (i == 0 || grid[i - 1][j] == 'W') {
                colCnt[j] = 0;
                for (int k = i; k < m && grid[k][j] != 'W'; ++k) {
                    colCnt[j] += (grid[k][j] == 'E');
                }
            }
            if (grid[i][j] == '0') {
                res = max(res, rowCnt + colCnt[j]);
            }
        }
    }
    return res;
}