Bomb Enemy

medium dp matrix

Problem

In a grid of 'E' (enemy), 'W' (wall), and '0' (empty), find the max number of enemies killed by placing a bomb on an empty cell. A bomb hits in four directions until a wall blocks.

Inputgrid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]

Output3

Placing at row 1 col 1 kills 3 enemies (up, down, left).

grid (rows ';' cells ',', 0/E/W)

def max_kill_enemies(grid):
    m, n = len(grid), len(grid[0])
    best = row_hits = 0
    col_hits = [0]*n
    for r in range(m):
        for c in range(n):
            if c == 0 or grid[r][c-1] == "W":
                row_hits = 0
                k = c
                while k < n and grid[r][k] != "W":
                    if grid[r][k] == "E": row_hits += 1
                    k += 1
            if r == 0 or grid[r-1][c] == "W":
                col_hits[c] = 0
                k = r
                while k < m and grid[k][c] != "W":
                    if grid[k][c] == "E": col_hits[c] += 1
                    k += 1
            if grid[r][c] == "0":
                best = max(best, row_hits + col_hits[c])
    return best

function maxKilledEnemies(grid) {
  const m = grid.length, n = grid[0].length;
  let best = 0, rowHits = 0;
  const colHits = new Array(n).fill(0);
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (c === 0 || grid[r][c-1] === "W") {
        rowHits = 0;
        for (let k = c; k < n && grid[r][k] !== "W"; k++) if (grid[r][k] === "E") rowHits++;
      }
      if (r === 0 || grid[r-1][c] === "W") {
        colHits[c] = 0;
        for (let k = r; k < m && grid[k][c] !== "W"; k++) if (grid[k][c] === "E") colHits[c]++;
      }
      if (grid[r][c] === "0") best = Math.max(best, rowHits + colHits[c]);
    }
  }
  return best;
}

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        int m = grid.length, n = grid[0].length, best = 0, rowHits = 0;
        int[] colHits = new int[n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (c == 0 || grid[r][c-1] == 'W') {
                    rowHits = 0;
                    for (int k = c; k < n && grid[r][k] != 'W'; k++) if (grid[r][k] == 'E') rowHits++;
                }
                if (r == 0 || grid[r-1][c] == 'W') {
                    colHits[c] = 0;
                    for (int k = r; k < m && grid[k][c] != 'W'; k++) if (grid[k][c] == 'E') colHits[c]++;
                }
                if (grid[r][c] == '0') best = Math.max(best, rowHits + colHits[c]);
            }
        }
        return best;
    }
}

int maxKilledEnemies(vector>& grid) {
    int m = grid.size(), n = grid[0].size(), best = 0, rowHits = 0;
    vector colHits(n, 0);
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (c == 0 || grid[r][c-1] == 'W') {
                rowHits = 0;
                for (int k = c; k < n && grid[r][k] != 'W'; k++) if (grid[r][k] == 'E') rowHits++;
            }
            if (r == 0 || grid[r-1][c] == 'W') {
                colHits[c] = 0;
                for (int k = r; k < m && grid[k][c] != 'W'; k++) if (grid[k][c] == 'E') colHits[c]++;
            }
            if (grid[r][c] == '0') best = max(best, rowHits + colHits[c]);
        }
    }
    return best;
}

Explanation

A bomb on an empty cell kills enemies in all four directions until a wall stops it. The naive way recounts each direction for every cell; the smart way is to cache the enemy count for the current horizontal and vertical segment and reuse it across cells in that same segment.

We scan the grid row by row. The variable rowHits holds the enemy count for the current horizontal stretch. We only recompute it when we are at the start of a new segment — that is, when c == 0 or the cell to the left is a wall grid[r][c-1] == "W". We then scan rightward to the next wall and count the E's.

Similarly colHits[c] caches the vertical count for column c, recomputed only when we hit the top of a new vertical segment (r == 0 or a wall above).

For every empty cell, the bomb's kills are simply rowHits + colHits[c], and we keep the maximum in best. Reusing the cached segment counts is what keeps this efficient.

Example: in the sample grid, placing the bomb at row 1 col 1 hits enemies up, down, and left — 3 kills, which is the best.

Time: O(mn) Space: O(n)