Lintcode 553. 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.

Example

Example1

Input:
grid =[
     "0E00",
     "E0WE",
     "0E00"
]
Output: 3
Explanation:
Placing a bomb at (1,1) kills 3 enemies

Example2

Input:
grid =[
     "0E00",
     "EEWE",
     "0E00"
]
Output: 2
Explanation:
Placing a bomb at (0,0) or (0,3) or (2,0) or (2,3) kills 2 enemies

Notice

You can only put the bomb at an empty cell.

Solution:
It's a DP problem. Think about the bomb direction can only go from up to down. So dp[i][j] means the number of enemies can kill in (i, j). 
Iniital state: dp[0][j] = 1 iff grid[0][j] == 'E'
transit function: dp[i][j] = dp[i - 1][j] + 1 // iff grid[i][j] = 'E'
dp[i][j] = dp[i-1][j] // iff grid[i][j] = '0'
dp[i][j] = 0 // iff grid[i][j] = 'W'

So it's the same case for other three directions. 

Code (Java):

public class Solution {
    /**
     * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
     * @return: an integer, the maximum enemies you can kill using one bomb
     */
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        // write your code here
        int m = grid.length;
        int n = grid[0].length;

        int[][] up = new int[m][n];
        int[][] down = new int[m][n];
        int[][] left = new int[m][n];
        int[][] right = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 'W') {
                    if (grid[i][j] == 'E') {
                        up[i][j] = 1;
                    }
                    if (i - 1 >= 0) {
                        up[i][j] += up[i - 1][j];
                    }
                }
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 'W') {
                    if (grid[i][j] == 'E') {
                        down[i][j] = 1;
                    }

                    if (i + 1 < m) {
                        down[i][j] += down[i + 1][j];
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 'W') {
                    if (grid[i][j] == 'E') {
                        left[i][j] = 1;
                    }
                    if (j - 1 >= 0) {
                        left[i][j] += left[i][j - 1];
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] != 'W') {
                    if (grid[i][j] == 'E') {
                       right[i][j] = 1;
                    }

                    if (j + 1 < n) {
                        right[i][j] += right[i][j + 1];
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    int num = up[i][j] + down[i][j] + left[i][j] + right[i][j];
                    ans = Math.max(ans, num);
                }
            }
        }

        return ans;
    }
}