You are given a rectangular grid representing a battlefield.
Each cell in the grid contains exactly one of the following values:
"W": a wall"E": an enemy"0": an empty cell, using the digit zero
You may place one bomb in one empty cell.
When the bomb is placed, it kills every enemy in the same row and the same column as the bomb position. However, the bomb effect stops in each direction when it reaches a wall because a wall cannot be destroyed.
Return the maximum number of enemies that can be killed by placing one bomb.
If there is no empty cell where a bomb can be placed, return
0.
The output is deterministic because only the maximum number of killed enemies is returned, not the bomb position.
Class Definition
Implement the class BombEnemy.
Method Signature
int maxKilledEnemies(List<String> grid)
grid is a list of strings representing the battlefield rows.- Each string represents one row of the grid.
- Inside each row string, cell values are separated by commas.
- Cell values inside a row contain no extra spaces.
- Each cell value is one of
"W", "E", or "0".
- The method returns the maximum number of enemies that can be killed by one bomb.
Input Format
The grid is represented as a List<String>.
For example, the row string "0,E,W,0" represents the row:
0 E W 0
If grid is empty, there are no cells in the battlefield.
Bomb Rules
- A bomb can be placed only on a cell containing
"0".
- The bomb kills enemies in the same row to the left and right of the bomb until a wall is reached.
- The bomb kills enemies in the same column above and below the bomb until a wall is reached.
- A wall blocks the bomb effect in that direction.
- The wall itself is never destroyed.
- Enemies behind a wall are not killed by the bomb.
- The bomb does not kill enemies diagonally.
Constraints
0 ≤ grid.size() ≤ 500- If
grid is empty, return 0.
- If
grid is not empty, 1 ≤ number of columns ≤ 500.
- If
grid is not empty, every row has the same number of comma-separated cells.
- Cell values inside a row are separated by commas and contain no extra spaces.
- Each cell value is exactly one of
"W", "E", or "0".
- The total number of cells is at most
250,000.
- No parameter value will be
null.
Examples
Example 1
BombEnemy bombEnemy = new BombEnemy()
bombEnemy.maxKilledEnemies(grid = ["0,E,0", "E,0,E", "0,E,0"])
Output:
4
Explanation:
Placing the bomb at the center cell kills one enemy above, one below, one left, and one right. Therefore, the maximum number of enemies killed is 4.
Example 2
BombEnemy bombEnemy = new BombEnemy()
bombEnemy.maxKilledEnemies(grid = ["0,E,0,0", "E,0,W,E", "0,E,0,0"])
Output:
3
Explanation:
One best placement is at row 1, column 1. It kills the enemy above, the enemy below, and the enemy to the left. The wall at row 1, column 2 blocks the bomb effect to the right. Therefore, the maximum number of enemies killed is 3.
Example 3
BombEnemy bombEnemy = new BombEnemy()
bombEnemy.maxKilledEnemies(grid = ["E,0,W,E", "0,0,W,0", "E,0,0,E"])
Output:
2
Explanation:
One best placement is at row 1, column 0. It kills one enemy above and one enemy below. Other empty cells can also kill at most two enemies. Therefore, the maximum number of enemies killed is 2.
Example 4
BombEnemy bombEnemy = new BombEnemy()
bombEnemy.maxKilledEnemies(grid = ["W,E,W", "E,W,E", "W,E,W"])
Output:
0
Explanation:
There is no empty cell containing "0", so no bomb can be placed.
Example 5
BombEnemy bombEnemy = new BombEnemy()
bombEnemy.maxKilledEnemies(grid = ["0,0,0", "0,W,0", "0,0,0"])
Output:
0
Explanation:
There are empty cells, but there are no enemies in the grid. Therefore, the maximum number of enemies killed is 0.
Example 6
BombEnemy bombEnemy = new BombEnemy()
bombEnemy.maxKilledEnemies(grid = [])
Output:
0
Explanation:
The grid is empty, so there is no empty cell where a bomb can be placed.