Question

Formatted question description: https://leetcode.ca/all/361.html

 361	Bomb Enemy

 Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero),
 return the maximum enemies you can kill using one bomb.

 The bomb kills all the enemies in the same row and column from the planted point
    until it hits the wall since the wall is too strong to be destroyed.

 Note that you can only put the bomb at an empty cell.

 Example:

 For the given grid

 0 E 0 0
 E 0 W E
 0 E 0 0

 return 3. (Placing a bomb at (1,1) kills 3 enemies)

 @tag-dp

Algorithm

Create four cumulative arrays v1, v2, v3, v4,

  • v1 is the cumulative array from left to right in the horizontal direction
  • v2 is the cumulative array from right to left in the horizontal direction
  • v3 is the cumulative array from top to bottom in the vertical direction
  • v4 is the cumulative array from bottom to top in the vertical direction

After building this cumulative array, for any position (i, j), the maximum number of enemies that can be killed is v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j], finally by comparing the cumulative sum of each position, you can get the result.

Code

Java

  • 
    public class Bomb_Enemy {
    
        public class Solution {
            public int maxKilledEnemies(char[][] grid) {
                if (grid == null || grid.length == 0) {
                    return 0;
                }
    
                int m = grid.length, n = grid[0].length, res = 0;
    
                int[][] v1 = new int[m][n];
                int[][] v2 = new int[m][n];
                int[][] v3 = new int[m][n];
                int[][] v4 = new int[m][n];
    
                for (int i = 0; i < m; ++i) {
                    for (int j = 0; j < n; ++j) { // left to right
                        int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
                        v1[i][j] = grid[i][j] == 'E' ? t + 1 : t; // @note: 没有关系,i-j 是0才可以放,不会是E
                    }
                    for (int j = n - 1; j >= 0; --j) { // right to left
                        int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
                        v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
                    }
                }
                for (int j = 0; j < n; ++j) {
                    for (int i = 0; i < m; ++i) { // up to down
                        int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
                        v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
                    }
                    for (int i = m - 1; i >= 0; --i) { // down to up
                        int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
                        v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
                    }
                }
    
                // final check
                for (int i = 0; i < m; ++i) {
                    for (int j = 0; j < n; ++j) {
                        if (grid[i][j] == '0') {
                            res = Math.max(res, v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]);
                        }
                    }
                }
                return res;
            }
        }
    
        public class Solution_2d {
            public int maxKilledEnemies(char[][] grid) {
                if (grid == null || grid.length == 0) {
                    return 0;
                }
    
                /*
                     enemyCount[i][0] stores the position of a certain W in the ith row,
                     enemyCount[i][1] stores the number of E from the W identified by enemyCount[i][0] to the previous W,
    
                     Initialization: enemyCount[i][0] = -1, enemyCount[i][1] = 0
                 */
                int[][] enemyCount = new int[grid.length][2];
    
                for (int i = 0; i < enemyCount.length; i++) {
                    enemyCount[i][0] = -1;
                }
    
                int max = 0;
                for (int j = 0; j < grid[0].length; j++) {
    
                    int colEnemy = countColEnemy(grid, j, 0);
    
                    for (int i = 0; i < grid.length; i++) {
                        // If the current position is the first one or the previous one is a wall, start traversing backward from the current position,
                        // Traverse to [end] or [wall] and stop, count the number of enemies
                        if (grid[i][j] == '0') { // ok to put bomb
                            if (j > enemyCount[i][0]) { // already over 1st wall of this row
                                update(enemyCount, grid, i, j);
                            }
                            max = Math.max(colEnemy + enemyCount[i][1], max);
                        }
                        if (grid[i][j] == 'W') {
                            colEnemy = countColEnemy(grid, j, i + 1);
                        }
                    }
    
                }
    
                return max;
            }
    
            private void update(int[][] enemyCount, char[][] grid, int i, int j) {
                int count = 0;
                int k = enemyCount[i][0] + 1;
                while (k < grid[0].length && (grid[i][k] != 'W' || k < j)) {
                    if (grid[i][k] == 'E') {
                        count += 1;
                    }
                    if (grid[i][k] == 'W') {
                        count = 0;
                    }
                    k += 1;
                }
                enemyCount[i][0] = k;
                enemyCount[i][1] = count;
            }
    
            private int countColEnemy(char[][] grid, int j, int start) {
                int count = 0;
                int i = start;
                while (i < grid.length && grid[i][j] != 'W') { // until next wall
                    if (grid[i][j] == 'E') {
                        count += 1;
                    }
                    i += 1;
                }
                return count;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/bomb-enemy/
    // Time: O(MN(M+N))
    // Space: O(1)
    class Solution {
    private:
        int M, N;
        int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
        int count(vector<vector<char>>& grid, int x, int y, int dir[2]) {
            int ans = 0;
            while (true) {
                x += dir[0];
                y += dir[1];
                if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] == 'W') break;
                if (grid[x][y] == 'E') ++ans;
            }
            return ans;
        }
        int count(vector<vector<char>>& grid, int x, int y) {
            int ans = 0;
            for (auto &dir : dirs) ans += count(grid, x, y, dir);
            return ans;
        }
    public:
        int maxKilledEnemies(vector<vector<char>>& grid) {
            if (grid.empty() || grid[0].empty()) return 0;
            M = grid.size();
            N = grid[0].size();
            int ans = 0;
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (grid[i][j] != '0') continue;
                    ans = max(ans, count(grid, i, j));
                }
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def maxKilledEnemies(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
          return 0
        dpRow = [[0] * (len(grid[0]) + 2) for _ in range(0, len(grid) + 2)]
        dpCol = [[0] * (len(grid[0]) + 2) for _ in range(0, len(grid) + 2)]
    
        for i in range(0, len(grid)):
          for j in range(0, len(grid[0])):
            dpRow[i + 1][j + 1] = dpRow[i + 1][j]
            dpCol[i + 1][j + 1] = dpCol[i][j + 1]
            if grid[i][j] == "W":
              dpRow[i + 1][j + 1] = 0
              dpCol[i + 1][j + 1] = 0
            if grid[i][j] == "E":
              dpRow[i + 1][j + 1] += 1
              dpCol[i + 1][j + 1] += 1
    
        maxKilled = 0
        for i in reversed(range(0, len(grid))):
          for j in reversed(range(0, len(grid[0]))):
            if grid[i][j] == "W":
              continue
            dpRow[i + 1][j + 1] = max(dpRow[i + 1][j + 1], dpRow[i + 1][j + 2])
            dpCol[i + 1][j + 1] = max(dpCol[i + 1][j + 1], dpCol[i + 2][j + 1])
            if grid[i][j] == "0":
              maxKilled = max(maxKilled, dpRow[i + 1][j + 1] + dpCol[i + 1][j + 1])
        return maxKilled
    
    

All Problems

All Solutions