[Leetcode] 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 that you can only put the bomb at an empty cell.

Example:

For the given grid

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

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

思路：

據說這道題目必須寫出時間複雜度是O(m*n)的算法才算過（m是grid的行個數，n是grid的列個數）。我開始想到的解法是比較原始的動态規劃，即定義四個二維數組left，right，up，down，分别表示它的某一個方向可以炸死多少個敵人，例如left[i][j]就表示如果在位置(i, j)放置一顆炸彈，可以炸死的左側的敵人個數；right，up和down的含義類似。計算這四個二維數組可以用動态規劃，花費的時間複雜度是O(m*n)。最後再用一個兩重循環确定max(left[i][j] + right[i][j] + up[i][j] + down[i][j])。然而這裡的空間複雜度高達O(4*m*n)，顯得很笨拙。

在網上看到一個很巧妙的算法，可以将空間複雜度降低到O(n)（當然再較真的話還可以降低到O(min(m, n))）。具體做法是：用二重循環周遊grid的時候，如果發現該格子處于第一行或者該格子的上面一個格子是牆，那麼就把從該位置到下方第一個牆（或者邊界）之間的敵人數目統計出來并且記錄下來；同理，如果發現該格子處于第一列或者該格子的左邊一個格子是牆，那麼就把從該位置到右方第一個牆（或者邊界）之間的敵人數目統計出來并且記錄下來。之後如果發現該位置是空位置，說明可以放炸彈，就更新最終結果。該方法的巧妙之處在于每個縱區間和每個橫區間内的敵人個數隻會被統計一次。是以雖然在代碼中兩重循環内部還有一重循環，但是由于有if條件語句的存在，實際上總的時間複雜度仍然是O(m*n)。

代碼：

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        int row = grid.size(), col = grid[0].size(), rowHits, colHits[col], ans = 0;  
        for(int i = 0; i < row; ++i) {  
            for(int j = 0; j < col; ++j) {  
                if(i == 0 || grid[i-1][j]=='W') {   // update colHits[j] only if the row starts from 0 or the up element is 'W'
                    colHits[j] = 0;  
                    for(int k = i; k < row && grid[k][j]!='W'; ++k) { 
                        colHits[j] += (grid[k][j] == 'E');  
                    }
                }  
                if(j == 0 || grid[i][j-1] == 'W') { // update rowHits only if the col start from 0 or the left element is 'W'
                    rowHits = 0;  
                    for(int k = j; k < col && grid[i][k]!='W'; ++k) { 
                        rowHits += (grid[i][k] == 'E');  
                    }
                }  
                if(grid[i][j] == '0') {
                    ans = max(ans, colHits[j] + rowHits);  
                }
            }  
        }  
        return ans;
    }
};