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

All Problems

All Solutions