#361
Medium Algorithms Bomb enemy
Array Dynamic Programming Matrix
52.8% acceptance
Mar 31, 2026
1003
118
No description available.
Solution
Rust
Time O(n³)
Space O(n)
impl Solution {
pub fn max_killed_enemies(grid: Vec<Vec<char>>) -> i32 {
if grid.is_empty() || grid[0].is_empty() {
return 0;
}
let m = grid.len();
let n = grid[0].len();
let mut col_hits = vec![0i32; n];
let mut row_hits;
let mut ans = 0;
for i in 0..m {
for j in 0..n {
// Recompute row_hits when at col 0 or just after a wall
if j == 0 || grid[i][j - 1] == 'W' {
row_hits = 0;
let mut k = j;
while k < n && grid[i][k] != 'W' {
if grid[i][k] == 'E' {
row_hits += 1;
}
k += 1;
}
} else {
// row_hits carries over
}
// Recompute col_hits[j] when at row 0 or just after a wall
if i == 0 || grid[i - 1][j] == 'W' {
col_hits[j] = 0;
let mut k = i;
while k < m && grid[k][j] != 'W' {
if grid[k][j] == 'E' {
col_hits[j] += 1;
}
k += 1;
}
}
if grid[i][j] == '0' {
// Need row_hits here; let's restructure
}
}
}
// Cleaner approach: precompute properly
let mut result = 0;
let mut col_kills = vec![0i32; n];
for i in 0..m {
let mut row_kill = 0i32;
for j in 0..n {
if j == 0 || grid[i][j - 1] == 'W' {
row_kill = 0;
let mut k = j;
while k < n && grid[i][k] != 'W' {
if grid[i][k] == 'E' { row_kill += 1; }
k += 1;
}
}
if i == 0 || grid[i - 1][j] == 'W' {
col_kills[j] = 0;
let mut k = i;
while k < m && grid[k][j] != 'W' {
if grid[k][j] == 'E' { col_kills[j] += 1; }
k += 1;
}
}
if grid[i][j] == '0' {
result = result.max(row_kill + col_kills[j]);
}
}
}
result
}
}