361. Bomb Enemy

Let count[i][j] be the maximum enemies that a bomb can kill in row i, col j. The naive solution will run O(m*n*(m+n)) time. The trick here to make it O(mn) is to keep a head and a tail variables. The head variable keeps the maximum enemies from left to grid[i][j] and the tail variable keeps the maximum enemies from the right to grid[i][j]. So for count[i][j], we want to add head if grid[i][j] is empty, i.e. grid[i][j] == 0 and for count[i][col-1-j], we want to add tail if grid[i][col-1-j] is empty. So when we traverse the row from 0 to col, we actually computes the maximum enemies for every position. Same for scanning columns. head is incremented by 1 if it finds an enemy or becomes 0 if it finds a wall. Same for tail.

1:  class Solution {  
2:  public:  
3:    int maxKilledEnemies(vector<vector<char>>& grid) {  
4:      int row = grid.size();  
5:      if (row == 0) return 0;  
6:      int col = grid[0].size();  
7:      vector<vector<int>> count(row, vector<int>(col, 0));  
8:      int i = 0, j = 0, head = 0, tail = 0;  
9:      for (i = 0; i < row; i++) {  
10:        for (j = head = tail = 0; j < col; j++) {  
11:          count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);  
12:          count[i][col-1-j] = grid[i][col-1-j] != '0' ? 0 : (count[i][col-1-j] + tail);  
13:          head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));  
14:          tail = grid[i][col-1-j] == 'W' ? 0 : (tail + (grid[i][col-1-j] == 'E' ? 1 : 0));  
15:        }  
16:      }  
17:      for (j = 0; j < col; j++) {  
18:        for (i = head = tail = 0; i < row; i++) {  
19:          count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);  
20:          count[row-1-i][j] = grid[row-1-i][j] != '0' ? 0 : (count[row-1-i][j] + tail);  
21:          head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));  
22:          tail = grid[row-1-i][j] == 'W' ? 0 : (tail + (grid[row-1-i][j] == 'E' ? 1 : 0));  
23:        }  
24:      }  
25:      int res = 0;  
26:      for (i = 0; i < row; i++) {  
27:        for (j = 0; j < col; j++) {  
28:          res = max(res, count[i][j]);  
29:        }  
30:      }  
31:      return res;  
32:    }  
33:  };