# Question

Formatted question description: https://leetcode.ca/all/361.html

Given an m x n matrix grid where each cell is either a wall 'W', an enemy 'E' or empty '0', return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.

Example 1:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3


Example 2:

Input: grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
Output: 1


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] is either 'W', 'E', or '0'.

# Algorithm

Create four cumulative arrays v1, v2, v3, v4,

• v1 is the cumulative array from left to right in the horizontal direction
• v2 is the cumulative array from right to left in the horizontal direction
• v3 is the cumulative array from top to bottom in the vertical direction
• v4 is the cumulative array from bottom to top in the vertical direction

After building this cumulative array, for any position (i, j), the maximum number of enemies that can be killed is v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j], finally by comparing the cumulative sum of each position, you can get the result.

# Code

• 
public class Bomb_Enemy {

public class Solution {
public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int m = grid.length, n = grid[0].length, res = 0;

int[][] v1 = new int[m][n];
int[][] v2 = new int[m][n];
int[][] v3 = new int[m][n];
int[][] v4 = new int[m][n];

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) { // left to right
int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
v1[i][j] = grid[i][j] == 'E' ? t + 1 : t; // @note: 没有关系，i-j 是0才可以放，不会是E
}
for (int j = n - 1; j >= 0; --j) { // right to left
int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) { // up to down
int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int i = m - 1; i >= 0; --i) { // down to up
int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}

// final check
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
res = Math.max(res, v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]);
}
}
}
return res;
}
}

public class Solution_2d {
public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

/*
enemyCount[i][0] stores the position of a certain W in the ith row,
enemyCount[i][1] stores the number of E from the W identified by enemyCount[i][0] to the previous W,

Initialization: enemyCount[i][0] = -1, enemyCount[i][1] = 0
*/
int[][] enemyCount = new int[grid.length][2];

for (int i = 0; i < enemyCount.length; i++) {
enemyCount[i][0] = -1;
}

int max = 0;
for (int j = 0; j < grid[0].length; j++) {

int colEnemy = countColEnemy(grid, j, 0);

for (int i = 0; i < grid.length; i++) {
// If the current position is the first one or the previous one is a wall, start traversing backward from the current position,
// Traverse to [end] or [wall] and stop, count the number of enemies
if (grid[i][j] == '0') { // ok to put bomb
if (j > enemyCount[i][0]) { // already over 1st wall of this row
update(enemyCount, grid, i, j);
}
max = Math.max(colEnemy + enemyCount[i][1], max);
}
if (grid[i][j] == 'W') {
colEnemy = countColEnemy(grid, j, i + 1);
}
}

}

return max;
}

private void update(int[][] enemyCount, char[][] grid, int i, int j) {
int count = 0;
int k = enemyCount[i][0] + 1;
while (k < grid[0].length && (grid[i][k] != 'W' || k < j)) {
if (grid[i][k] == 'E') {
count += 1;
}
if (grid[i][k] == 'W') {
count = 0;
}
k += 1;
}
enemyCount[i][0] = k;
enemyCount[i][1] = count;
}

private int countColEnemy(char[][] grid, int j, int start) {
int count = 0;
int i = start;
while (i < grid.length && grid[i][j] != 'W') { // until next wall
if (grid[i][j] == 'E') {
count += 1;
}
i += 1;
}
return count;
}
}
}

############

class Solution {
public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] g = new int[m][n];
for (int i = 0; i < m; ++i) {
int t = 0;
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
t = 0;
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
}
for (int j = 0; j < n; ++j) {
int t = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
t = 0;
for (int i = m - 1; i >= 0; --i) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
ans = Math.max(ans, g[i][j]);
}
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/bomb-enemy/
// Time: O(MN(M+N))
// Space: O(1)
class Solution {
private:
int M, N;
int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int count(vector<vector<char>>& grid, int x, int y, int dir[2]) {
int ans = 0;
while (true) {
x += dir[0];
y += dir[1];
if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] == 'W') break;
if (grid[x][y] == 'E') ++ans;
}
return ans;
}
int count(vector<vector<char>>& grid, int x, int y) {
int ans = 0;
for (auto &dir : dirs) ans += count(grid, x, y, dir);
return ans;
}
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
M = grid.size();
N = grid[0].size();
int ans = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] != '0') continue;
ans = max(ans, count(grid, i, j));
}
}
return ans;
}
};

• class Solution:
def maxKilledEnemies(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
g = [[0] * n for _ in range(m)]
for i in range(m):
t = 0
for j in range(n):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
t = 0
for j in range(n - 1, -1, -1):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
for j in range(n):
t = 0
for i in range(m):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
t = 0
for i in range(m - 1, -1, -1):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
return max(
[g[i][j] for i in range(m) for j in range(n) if grid[i][j] == '0'],
default=0,
)

############

class Solution(object):
def maxKilledEnemies(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0
dpRow = [[0] * (len(grid[0]) + 2) for _ in range(0, len(grid) + 2)]
dpCol = [[0] * (len(grid[0]) + 2) for _ in range(0, len(grid) + 2)]

for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
dpRow[i + 1][j + 1] = dpRow[i + 1][j]
dpCol[i + 1][j + 1] = dpCol[i][j + 1]
if grid[i][j] == "W":
dpRow[i + 1][j + 1] = 0
dpCol[i + 1][j + 1] = 0
if grid[i][j] == "E":
dpRow[i + 1][j + 1] += 1
dpCol[i + 1][j + 1] += 1

maxKilled = 0
for i in reversed(range(0, len(grid))):
for j in reversed(range(0, len(grid[0]))):
if grid[i][j] == "W":
continue
dpRow[i + 1][j + 1] = max(dpRow[i + 1][j + 1], dpRow[i + 1][j + 2])
dpCol[i + 1][j + 1] = max(dpCol[i + 1][j + 1], dpCol[i + 2][j + 1])
if grid[i][j] == "0":
maxKilled = max(maxKilled, dpRow[i + 1][j + 1] + dpCol[i + 1][j + 1])
return maxKilled


• func maxKilledEnemies(grid [][]byte) int {
m, n := len(grid), len(grid[0])
g := make([][]int, m)
for i := range g {
g[i] = make([]int, n)
}
for i := 0; i < m; i++ {
t := 0
for j := 0; j < n; j++ {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
t = 0
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
}
for j := 0; j < n; j++ {
t := 0
for i := 0; i < m; i++ {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
t = 0
for i := m - 1; i >= 0; i-- {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
}
ans := 0
for i, row := range grid {
for j, v := range row {
if v == '0' && ans < g[i][j] {
ans = g[i][j]
}
}
}
return ans
}