Question
Given an m x n
matrix grid
where each cell is either a wall 'W'
, an enemy 'E'
or empty '0'
, return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.
Example 1:
Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3
Algorithm

Use brute force, iterate all the grids and calculated the row and column for each grid, time complexity would be O(m*n*(m+n));

We could know form the brute force way we actually repeatedly calculated the enemy can be killed for each grid in a row. So only keep the row hit and column hit. The time is O(m*n);

We have two case:
 Start from start and stop when meeting an wall or the end of grid;
 Start from a cell after wall and stop at a wall or the end of grid;

We still iterate all the grids but rather than recalculate for each cell, we store the intermediate results such as
row_hits
andcol_hits
and reuse them whenever possible. 
For the
row_hits
value, it suffices to use one variable for all the cells on the same row, since we iterate over the grid from left to right and we don't need to memorize therow_hits
value for the previous row.As to the
col_hits
value, we need to use an array to keep track of all thecol_hits
values, since we need to go over all the columns for each row.

Code
class Solution { public int maxKilledEnemies(char[][] grid) { if (grid.length == 0) return 0; int rows = grid.length; int cols = grid[0].length; int maxCount = 0, rowHits = 0; int[] colHits = new int[cols]; for (int row = 0; row < rows; ++row) { for (int col = 0; col < cols; ++col) { // reset the hits on the row, if necessary. if (col == 0  grid[row][col  1] == 'W') { rowHits = 0; for (int k = col; k < cols; ++k) { if (grid[row][k] == 'W') // stop the scan when we hit the wall. break; else if (grid[row][k] == 'E') rowHits += 1; } } // reset the hits on the column, if necessary. if (row == 0  grid[row  1][col] == 'W') { colHits[col] = 0; for (int k = row; k < rows; ++k) { if (grid[k][col] == 'W') break; else if (grid[k][col] == 'E') colHits[col] += 1; } } // run the calculation for the empty cell. if (grid[row][col] == '0') { maxCount = Math.max(maxCount, rowHits + colHits[col]); } } } return maxCount; } }
Well for me this question is nothing special but a little hard to implement in an efficient way.