Bomb Enemy

Problem Statement

In the given problem, an m x n matrix named grid is provided. Each cell within this matrix can either contain:

• A wall, represented by 'W'
• An enemy, represented by 'E'
• An empty space, represented by '0'

The task is to determine the maximum number of enemies that can be eliminated using a single bomb placement. It's important to note that the bomb can only be placed in an empty cell ('0'). Once placed, the bomb will destroy all enemies located directly in the same row and column as the bomb, until its path is obstructed by a wall ('W'). This setup requires strategic placement of the bomb to maximize enemy casualties, considering the configuration of walls and empty spaces that influence the bomb's effective range.

Examples

Example 1

Input:

grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]

Output:

3

Example 2

Input:

grid = [["W","W","W"],["0","0","0"],["E","E","E"]]

Output:

1

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] is either 'W', 'E', or '0'.

Approach and Intuition

The approach to solve this problem is closely tied to understanding the distribution of enemies and walls within the grid, combined with strategic placement of the bomb on empty cells. Here is a step-by-step breakdown of how one might think about the problem:

1. Iterate through the matrix: Traverse each cell in the grid to check potential bomb placement sites (empty cells).

2. Calculate damage for each empty cell:

   • For each empty cell that you encounter ('0'), calculate the total number of enemies ('E') that can be destroyed both in its row and column.
   • Ensure that the count stops if a wall ('W') is encountered since the bomb's effect will not pass through walls.

3. Tracking maximum damage:

   • For every empty cell evaluated, keep track of the maximum number of enemies that can be destroyed from that point.
   • Update this maximum whenever you encounter a higher potential kill count from another empty cell.

4. Return the highest count discovered.

   • After evaluating all possible empty cells, the highest recorded count will represent the maximum number of enemies that one could destroy using a bomb.

This approach ensures that we are checking each possible bomb placement for its effectiveness before deciding on the optimal placement to kill the maximum number of enemies. Each step is crucial, as overlooking even a single row or column can lead to sub-optimal answers. This method leverages a thorough examination combined with strategic calculation to solve the problem efficiently.

Solutions

class Solution {
    public int maxEnemiesDestroyed(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
    
        int totalRows = matrix.length;
        int totalCols = matrix[0].length;
    
        int maxEnemies = 0, rowEnemies = 0;
        int[] colEnemies = new int[totalCols];
    
        for (int i = 0; i < totalRows; ++i) {
            for (int j = 0; j < totalCols; ++j) {
    
                // Reset row enemies count if needed
                if (j == 0 || matrix[i][j - 1] == 'W') {
                    rowEnemies = 0;
                    for (int x = j; x < totalCols; ++x) {
                        if (matrix[i][x] == 'W')
                            break;
                        else if (matrix[i][x] == 'E')
                            rowEnemies += 1;
                    }
                }
    
                // Reset column enemies count if needed
                if (i == 0 || matrix[i - 1][j] == 'W') {
                    colEnemies[j] = 0;
                    for (int x = i; x < totalRows; ++x) {
                        if (matrix[x][j] == 'W')
                            break;
                        else if (matrix[x][j] == 'E')
                            colEnemies[j] += 1;
                    }
                }
    
                // Calculate maximum for empty cell
                if (matrix[i][j] == '0') {
                    maxEnemies = Math.max(maxEnemies, rowEnemies + colEnemies[j]);
                }
            }
        }
    
        return maxEnemies;
    }
}