361. Bomb Enemy

Description

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)

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

Solution

Iteration, O(mn * (m + n)), S(1)

从grid中的任意一个'0'点开始，向上下左右四个方向笔直扩散，统计'E'数量，遇到'W'该方向就停止。

class Solution {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        int max = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] != '0') {
                    continue;
                }
                
                int count = 0;
                
                for (int[] d : DIRECTIONS) {
                    for (int x = i + d[0], y = j + d[1]; 
                         isValid(grid, x, y) && grid[x][y] != 'W'; 
                         x += d[0], y += d[1]) {
                        if (grid[x][y] == 'E') {
                            ++count;
                        }
                    }
                }
                
                max = Math.max(count, max);
            }
        }
        
        return max;
    }
    
    private boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}

DP, O(mn), S(mn)

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        int[][][] dp = new int[m][n][4];
        // dp[i][j][0] means enemies count in the left (including (i, j) itself)
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'W') {
                    continue;
                }
                dp[i][j][0] = (grid[i][j] == 'E' ? 1 : 0) + (i > 0 ? dp[i - 1][j][0] : 0);
                dp[i][j][1] = (grid[i][j] == 'E' ? 1 : 0) + (j > 0 ? dp[i][j - 1][1] : 0);
            }
        }
        
        int max = 0;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 'W') {
                    continue;
                }
                dp[i][j][2] = (grid[i][j] == 'E' ? 1 : 0) + (i < m - 1 ? dp[i + 1][j][2] : 0);
                dp[i][j][3] = (grid[i][j] == 'E' ? 1 : 0) + (j < n - 1 ? dp[i][j + 1][3] : 0);
                
                if (grid[i][j] == '0') {  // imporant! Because we can only put bomb at empty slot
                    max = Math.max(IntStream.of(dp[i][j]).sum(), max);
                }
            }
        }
        
        return max;
    }
}