Bomb Enemy
Medium · 1-D Dynamic Programming · Explanation and code example
Four Directional Sweeps
How it works
For each empty cell, count visible enemies along its row and column until a wall. Four sweeps accumulate enemies from the left, right, top, and bottom. Reset the running count at every wall and add it only at empty cells.
Steps
- Sweep each row in both directions.
- Sweep each column in both directions.
- Return the largest accumulated empty-cell count.
Complexity
- Time: O(rows × columns).
- Space: O(rows × columns).
Things to watch for
- Walls stop visibility.
- Enemies cannot host a bomb.
- Reset counts at the start of each new row or column.
Python code example
class Solution:
def maxKilledEnemies(self, grid: list[list[str]]) -> int:
m = len(grid)
n = len(grid[0])
enemyCount = 0
# dp[i][j] := the maximum 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 the 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)
# Returns sum(map(sum, dp))
return max(map(max, dp))
C++ code example
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] := the maximum 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 the 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(dp.begin(), dp.end(), 0,
[](int acc, const vector<int>& row) {
return max(acc, ranges::max(row));
});
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.