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.

答案

做了这么些dp题，发现题目看上去稍微复杂，没看出递归解的规律的话一般就知道要曲线救国，通过动态填写其他信息，填写完后可以根据这些信息来解答题目所求

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if(grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int[][][] f = new int[m][n][4];
        // f[i][j][0]: how many enemy on the left of grid[i][j] until next wall, inclusive

        for(int i = 0; i < m; i++) {
            int left = 0, right = 0;
            for(int j = 0; j < n; j++) {
                int k = n - j - 1;
                left = (grid[i][j] == 'W') ? (0) : ((grid[i][j] == 'E') ? left + 1 : left);
                right = (grid[i][k] == 'W') ? (0) : ((grid[i][k] == 'E') ? right + 1 : right);
                f[i][j][0] = left;
                f[i][k][1] = right;
            }
        }

        for(int i = 0; i < n; i++) {
            int up = 0, down = 0;
            for(int j = 0; j < m; j++) {
                int k = m - j - 1;
                up = (grid[j][i] == 'W') ? (0) : ((grid[j][i] == 'E') ? up + 1 : up);
                down = (grid[k][i] == 'W') ? (0) : ((grid[k][i] == 'E') ? down + 1 : down);
                f[j][i][2] = up;
                f[k][i][3] = down;
            }
        }
        
        int max = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] != '0') continue;
                int curr = f[i][j][0] + f[i][j][1] + f[i][j][2] + f[i][j][3];
                if(curr > max) max = curr;
            }
        }
        return max;
    }
}