LeetCode Solutions

			

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] := max 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 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(begin(dp), end(dp), 0, [](int s, vector<int>& row) {
      return max(s, *max_element(begin(row), end(row)));
    });
  }
};

			

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;
    int ans = 0;
    // dp[i][j] := max enemies grid[i][j] can kill
    int[][] dp = new int[m][n];

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

    for (int[] row : dp)
      ans = Math.max(ans, Arrays.stream(row).max().getAsInt());

    return ans;
  }

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

			

class Solution:
  def maxKilledEnemies(self, grid: List[List[chr]]) -> int:
    m = len(grid)
    n = len(grid[0])
    enemyCount = 0
    # dp[i][j] := max 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 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))