361. Bomb Enemy

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.

-------------------------
很直接的遍历。row里存的是当前横向杀人的敌人个数，cols[j]存的是在col j杀伤的敌人个数
只有在前一位是'W'的时候，才会检查杀伤到多少敌人

O(m * n) time, O(n) space

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid.length == 0) return 0;
        int max = 0;
        int row = 0;
        int[] cols = new int[grid[0].length];
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 'W') continue;
                if (j == 0 || grid[i][j - 1] == 'W') {
                    row = getRow(grid, i, j);
                }
                
                if (i == 0 || grid[i - 1][j] == 'W') {
                    cols[j] = getCol(grid, i, j);
                }
                
                if (grid[i][j] == '0' && row + cols[j] > max) {
                    max = row + cols[j];
                }
            }
        }
        
        return max;
    }
    
    private int getRow(char[][] grid, int i, int j) {
        int rt = 0;
        while (j < grid[0].length && grid[i][j] != 'W') {
            if (grid[i][j] == 'E') rt++;
            j++;
        }
        
        return rt;
    }
    
    private int getCol(char[][] grid, int i, int j) {
        int rt = 0;
        while (i < grid.length && grid[i][j] != 'W') {
            if (grid[i][j] == 'E') rt++;
            i++;
        }
        
        return rt;
    }
}