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:

1
2
3
4
5
6
7
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)

left2right, right2left, top2bottom, bottom2top, 指从相应方向过来的不包含当前cell的enemy的数量.
这样在一个值’0’的cell上放置炸弹, 能炸到的enemy的数量就是left2right + right2left + top2bottom + bottom2top

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public int maxKilledEnemies(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0)
        return 0;
    int ans = 0;
    int m = grid.length, n = grid[0].length;
    int[][] left2right = new int[m][n];
    int[][] right2left = new int[m][n];
    int[][] top2bottom = new int[m][n];
    int[][] bottom2top = new int[m][n];
    // calculate left2right and right2left
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int k = n - 1 - j;
            if (grid[i][j] == 'W') {
                left2right[i][j] = 0;
            } else {
                if (j > 0) {
                    left2right[i][j] = left2right[i][j - 1] + (grid[i][j - 1] == 'E' ? 1 : 0);
                }
            }
            if (grid[i][k] == 'W') {
                right2left[i][k] = 0;
            } else {
                if (k < n - 1) {
                    right2left[i][k] = right2left[i][k + 1] + (grid[i][k + 1] == 'E' ? 1 : 0);
                }
            }
        }
    }
    // calculate top2bottom and bottom2top
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; i++) {
            if (grid[i][j] == 'W') {
                top2bottom[i][j] = 0;
            } else {
                if (i > 0)
                    top2bottom[i][j] = top2bottom[i - 1][j] + (grid[i - 1][j] == 'E' ? 1 : 0);
            }
            int k = m - 1 - i;
            if (grid[k][j] == 'W') {
                bottom2top[k][j] = 0;
            } else {
                if (k < m - 1)
                    bottom2top[k][j] = bottom2top[k + 1][j] + (grid[k + 1][j] == 'E' ? 1 : 0);
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '0') {
                int count = left2right[i][j] + right2left[i][j] + top2bottom[i][j] + bottom2top[i][j];
                ans = Math.max(ans, count);
            }
        }
    }
    return ans;
}