Skip to content

361. Bomb Enemy 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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 subtotal, const vector<int>& row) {
      return max(subtotal, ranges::max(row));
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
    // dp[i][j] := the maximum enemies grid[i][j] can kill
    int[][] dp = new int[m][n];

    // 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(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);
    }

    return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
  }

  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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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))