L 361. Bomb Enemy ----M

 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.

A:

就是一行行数， 

如果遇到0， 就把其位置存起来。 直到走到边缘或者遇到墙。 则把所有的0 都填上 W的个数

再一列列数。这时候，如果遇到了W或者边缘， 就直接计算其0  位置的和 即可，不需要保存。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

class Solution { public: int maxKilledEnemies(vector<vector<char>>& grid) { int m = grid.size(); if(m==0) return 0; int n = grid[0].size(); vector<vector<int>> V(m,vector<int>(n,0)); for(int i =0;i<m;i++){ vector<int> emptyCol; int preWCount = 0; for(int j = 0;j<= n;j++){ if(j==n || grid[i][j]=='W'){ for(auto k : emptyCol){ V[i][k] = preWCount; } preWCount=0; emptyCol.clear(); }else if(grid[i][j] == '0'){ emptyCol.push_back(j); }else if( grid[i][j] == 'E' ){ preWCount++; } } } int res = 0; // calculate column by column for(int j = 0;j<n;j++){ vector<int> emptyRow; int preWCount = 0; for(int i =0;i<=m;i++){ if(i==m || grid[i][j]=='W'){ for(auto k : emptyRow){ res = max(res, V[k][j] + preWCount); } preWCount=0; emptyRow.clear(); }else if(grid[i][j] == '0'){ emptyRow.push_back(i); }else if( grid[i][j] == 'E' ){ preWCount++; } } } return res; } };