0361. Bomb Enemy
https://leetcode.com/problems/bomb-enemy
Description
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'
.
ac
class Solution {
public int maxKilledEnemies(char[][] grid) {
// edge cases
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int row = grid.length;
int col = grid[0].length;
// dp memorize cnt
int[][] cnt = new int[row][col];
int[] hori = new int[row];
int[] verti = new int[col];
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == '0') {
cnt[r][c] = hori[r] + verti[c];
}
else if (grid[r][c] == 'W') {
hori[r] = 0;
verti[c] = 0;
}
else {
hori[r]++;
verti[c]++;
}
}
}
// 2nd pass, backward, get max
hori = new int[row];
verti = new int[col];
int max = 0;
for (int r = row-1; r >= 0; r--) {
for (int c = col-1; c >= 0; c--) {
if (grid[r][c] == '0') {
cnt[r][c] += hori[r] + verti[c];
max = Math.max(max, cnt[r][c]);
}
else if (grid[r][c] == 'W') {
hori[r] = 0;
verti[c] = 0;
}
else {
hori[r]++;
verti[c]++;
}
}
}
return max;
}
}
/*
2 pass
*/
Last updated
Was this helpful?