361. Bomb Enemy

Published on June 24, 2023

Question

Given an m x n matrix grid where each cell is either a wall 'W', an enemy 'E' or empty '0', return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell.

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

Example 1:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

Algorithm

Use brute force, iterate all the grids and calculated the row and column for each grid, time complexity would be O(m*n*(m+n));
We could know form the brute force way we actually repeatedly calculated the enemy can be killed for each grid in a row. So only keep the row hit and column hit. The time is O(m*n);
1. We have two case:
  1. Start from start and stop when meeting an wall or the end of grid;
  2. Start from a cell after wall and stop at a wall or the end of grid;
2. We still iterate all the grids but rather than recalculate for each cell, we store the intermediate results such as row_hits and col_hits and reuse them whenever possible.
3. For the row_hits value, it suffices to use one variable for all the cells on the same row, since we iterate over the grid from left to right and we don't need to memorize the row_hits value for the previous row.
  
  As to the col_hits value, we need to use an array to keep track of all the col_hits values, since we need to go over all the columns for each row.

Code

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid.length == 0)
            return 0;

        int rows = grid.length;
        int cols = grid[0].length;

        int maxCount = 0, rowHits = 0;
        int[] colHits = new int[cols];

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {

                // reset the hits on the row, if necessary.
                if (col == 0 || grid[row][col - 1] == 'W') {
                    rowHits = 0;
                    for (int k = col; k < cols; ++k) {
                        if (grid[row][k] == 'W')
                            // stop the scan when we hit the wall.
                            break;
                        else if (grid[row][k] == 'E')
                            rowHits += 1;
                    }
                }

                // reset the hits on the column, if necessary.
                if (row == 0 || grid[row - 1][col] == 'W') {
                    colHits[col] = 0;
                    for (int k = row; k < rows; ++k) {
                        if (grid[k][col] == 'W')
                            break;
                        else if (grid[k][col] == 'E')
                            colHits[col] += 1;
                    }
                }

                // run the calculation for the empty cell.
                if (grid[row][col] == '0') {
                    maxCount = Math.max(maxCount, rowHits + colHits[col]);
                }
            }
        }

        return maxCount;
    }
}

Well for me this question is nothing special but a little hard to implement in an efficient way.