361. Bomb Enemy

/**

 * 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: You can only put the bomb at

 * an empty cell.

 *

 * Example:

 *

 * Input: [[“0″,”E”,”0″,”0″],[“E”,”0″,”W”,”E”],[“0″,”E”,”0″,”0″]] Output: 3 Explanation: For the given grid,

 *

 * 0 E 0 0 E 0 W E 0 E 0 0

*/

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/BombEnemy.java

Observation:

              We can traverse the maze for each cell repeatedly to calculate the number of cells that can be bombed but we will be repeating work. A more efficient approach is to use dynamic programming where we can track the previously calculated cells that can be bombed and reuse that knowledge for subsequent cells.

              We can traverse the maze incrementally per rows and columns. Traverse the row horizontally for all columns until we find a wall while tracking number of enemies between the given cell and the next wall in the row. And repeat the same for each column we traverse, calculate number of enemies bombed until we hit a wall. That way we can reuse the previously calculated value. When the prior column or row is a wall, we repeat the enemy calculation for the cell and row.

Logic:

• Iterate from first row and column on to last row and last column
  • If the given row/col is a wall skip it
  • If it’s the first column or the prior column on given row was a wall calculate number of enemies that can be bombed from given row
  • If it’s the first row or the given column on prior row was a wall recalculate the number of enemies that can be bombed
  • Per above, number of enemies that can be bombed in a row can be calculated in a single variable but need an array to store number of columns that can be bombed as when we iterate over columns left to right, number of enemies that can be bombed per column (vertically) is intendent of the previous column
  • Calculate the total based on vertical and horizontal bombable enemies and update max variable

Here is the code:

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

    int rowCt = 0;
    int[] colCts = new int[cols];

    for (int row = 0; row < grid.length; row++) {
        for (int col = 0; col < grid[0].length; col++) {
            if (grid[row][col] == 'W') {
                continue;
            }

            //at the first column or when the prior column was a Wall , reset
            if ((col == 0) || grid[row][col - 1] == 'W') {
                rowCt = 0;
                for (int i = col; i < cols; i++) {
                    if (grid[row][i] == 'W') {
                        break;
                    }
                    if (grid[row][i] == 'E') {
                        rowCt++;
                    }
                }
            }

            //reset on first row or when prior row had a wall
            if ((row == 0) || grid[row - 1][col] == 'W') {
                colCts[col] = 0;
                for (int i = row; i < rows; i++) {
                    if (grid[i][col] == 'W') {
                        break;
                    }
                    if (grid[i][col] == 'E') {
                        colCts[col]++;
                    }
                }
            }

            if (grid[row][col] == '0') {
                this.max = Math.max(max, rowCt + colCts[col]);
            }
        }
    }
    return max;
}