Bomb Enemy

题目地址：
https://leetcode.com/problems/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)

解题思路：
这道题就是用一个Spot的class来存有4个方向可以炸到的enemy的个数。

代码：

public class BombEnemy {

    /*    ["0E00",     "E0WE",     "0E00"]
    ["0E00",     "EEWE",     "0E00"]
    * */
    public static void main(String[] args){
        BombEnemy bombEnemy = new BombEnemy();
        char[][] board = {{'0', 'E', '0', '0'}, {'E', 'E', 'W', 'E'}, {'0', 'E', '0', '0'}};
        int rst = bombEnemy.maxKilledEnemies(board);
        System.out.println(rst);
    }

    class Spot {
        int up;
        int down;
        int left;
        int right;
    }

    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        Spot[][] dp = new Spot[m][n];
        for(int i = 0; i <= m - 1; i++){
            for(int j = 0; j <= n - 1; j++){
                dp[i][j] = new Spot();
                if(grid[i][j] == 'W'){
                    continue;
                }
                dp[i][j].up = (i == 0 ? 0 : dp[i - 1][j].up) + (grid[i][j] == 'E' ? 1 : 0);
                dp[i][j].left = (j == 0 ? 0 : dp[i][j - 1].left) + (grid[i][j] == 'E' ? 1 : 0);
            }
        }
        int rst = 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].down = (i == m - 1 ? 0 : dp[i + 1][j].down) + (grid[i][j] == 'E' ? 1 : 0);
                dp[i][j].right = (j == n - 1 ? 0 : dp[i][j + 1].right) + (grid[i][j] == 'E' ? 1 : 0);
                if(grid[i][j] == '0'){
                    rst = Math.max(rst, dp[i][j].left + dp[i][j].right + dp[i][j].up + dp[i][j].down);
                }
                // for the follow up if the bomb could be placed on the enemy//                if(grid[i][j] == 'E'){//                    rst = Math.max(rst, dp[i][j].left + dp[i][j].right + dp[i][j].up + dp[i][j].down - 3);//                }            }
        }
        return rst;
    }
}