• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
int enemyCount = 0;
// dp[i][j] := max enemies grid[i][j] can kill
vector<vector<int>> dp(m, vector<int>(n));

auto update = [&](int i, int j) {
if (grid[i][j] == '0')
dp[i][j] += enemyCount;
else if (grid[i][j] == 'E')
++enemyCount;
else  // grid[i][j] == 'W'
enemyCount = 0;
};

// extend four directions, if meet 'W', need to start over from 0
for (int i = 0; i < m; ++i) {
enemyCount = 0;
for (int j = 0; j < n; ++j)
update(i, j);
enemyCount = 0;
for (int j = n - 1; j >= 0; --j)
update(i, j);
}

for (int j = 0; j < n; ++j) {
enemyCount = 0;
for (int i = 0; i < m; ++i)
update(i, j);
enemyCount = 0;
for (int i = m - 1; i >= 0; --i)
update(i, j);
}

return accumulate(begin(dp), end(dp), 0, [](int s, vector<int>& row) {
return max(s, *max_element(begin(row), end(row)));
});
}
};
``````

## JAVA

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

final int m = grid.length;
final int n = grid[0].length;
int ans = 0;
// dp[i][j] := max enemies grid[i][j] can kill
int[][] dp = new int[m][n];

// extend four directions, if meet 'W', need to start over from 0
for (int i = 0; i < m; ++i) {
enemyCount = 0;
for (int j = 0; j < n; ++j)
update(grid, i, j, dp);
enemyCount = 0;
for (int j = n - 1; j >= 0; --j)
update(grid, i, j, dp);
}

for (int j = 0; j < n; ++j) {
enemyCount = 0;
for (int i = 0; i < m; ++i)
update(grid, i, j, dp);
enemyCount = 0;
for (int i = m - 1; i >= 0; --i)
update(grid, i, j, dp);
}

for (int[] row : dp)
ans = Math.max(ans, Arrays.stream(row).max().getAsInt());

return ans;
}

private int enemyCount = 0;

private void update(char[][] grid, int i, int j, int[][] dp) {
if (grid[i][j] == '0')
dp[i][j] += enemyCount;
else if (grid[i][j] == 'E')
++enemyCount;
else // grid[i][j] == 'W'
enemyCount = 0;
}
}
``````

## Python

``````class Solution:
def maxKilledEnemies(self, grid: List[List[chr]]) -> int:
m = len(grid)
n = len(grid[0])
enemyCount = 0
# dp[i][j] := max enemies grid[i][j] can kill
dp = [[0] * n for _ in range(m)]

def update(i: int, j: int) -> None:
nonlocal enemyCount
if grid[i][j] == '0':
dp[i][j] += enemyCount
elif grid[i][j] == 'E':
enemyCount += 1
else:  # grid[i][j] == 'W'
enemyCount = 0

# extend four directions, if meet 'W', need to start over from 0
for i in range(m):
enemyCount = 0
for j in range(n):
update(i, j)
enemyCount = 0
for j in reversed(range(n)):
update(i, j)

for j in range(n):
enemyCount = 0
for i in range(m):
update(i, j)
enemyCount = 0
for i in reversed(range(m)):
update(i, j)

# return sum(map(sum, dp))
return max(map(max, dp))
``````