301. Bomb Enemy
You receive an m × n grid of characters, one of three kinds per cell: 'E' is an enemy, 'W' is a wall, and '0' is an empty cell.
You may drop exactly one bomb, and only on an empty cell. The blast shoots out from that cell along its row and its column, in all four directions, destroying every enemy it reaches — but it cannot pass through a wall (the wall survives and shields everything behind it). Enemies do not block the blast.
Return a single integer: the largest number of enemies one well-placed bomb can destroy. If the grid contains no empty cell, return 0.
Example 1:
Input: grid = ["0E00","E0WE","0E00"]
Output: 3
Explanation: Bombing row 1, column 1 destroys the enemy above it, the enemy below it, and the enemy to its left — the wall at row 1, column 2 shields the enemy on the far right.
Example 2:
Input: grid = ["EEE","E0E","EEE"]
Output: 4
Explanation: The only empty cell is the center. Its blast reaches one enemy in each of the four directions; the four corner enemies share no row or column with it.
Constraints:
- 1 ≤ m, n ≤ 500
- Every cell is one of '0', 'E', 'W'
- The bomb may only be placed on a '0' cell; if there is none, the answer is 0.
Hints:
For one empty cell the damage is easy: walk up, down, left, and right, counting enemies until a wall or the edge stops you. Doing that for every empty cell works — how much does it cost?
Notice how much work repeats: every cell between the same two walls in a row sees the *same* row damage. Compute the enemy count once per wall-to-wall segment, when you enter it, and reuse it until the next wall.
Keep one running `rowKills` and an array `colKills[n]`, each recomputed only at a segment start (column 0 / row 0 or just after a wall). At every empty cell the answer candidate is `rowKills + colKills[c]` — an O(m·n) sweep overall.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = ["0E00","E0WE","0E00"]
Expected output: 3