**Solution**

**Bomb Enemy** https://leetcode.com/problems/bomb-enemy/

**Brute Force Solution**

- There is an obvious brute force solution where we start from each 0 and scan the row and column. We need to be careful in doing this count - move right and then move left. Similarly move up and move down. Complexity of this solution is O(mn(m+n)).

```
class Solution(object):
def scan_vertical(self, i,j,grid, direction):
N, M = len(grid), len(grid[0])
cnt = 0
while 0<=i<N and grid[i][j] != "W":
cnt = cnt + 1 if grid[i][j] == "E" else cnt
i = i + 1 if direction == "D" else i-1
return cnt
def scan_horizontal(self, i,j,grid, direction):
N, M = len(grid), len(grid[0])
cnt = 0
while 0<=j<M and grid[i][j] != "W":
cnt = cnt + 1 if grid[i][j] == "E" else cnt
j = j + 1 if direction == "R" else j-1
return cnt
def maxKilledEnemies(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid == []:
return 0
N, M = len(grid), len(grid[0])
max_bomb_enemy = 0
for i in range(N):
for j in range(M):
if grid[i][j] == "0":
c = self.scan_vertical(i,j,grid, "D") + self.scan_vertical(i,j,grid, "U")
c = c + self.scan_horizontal(i,j,grid, "L") + self.scan_horizontal(i,j,grid, "R")
max_bomb_enemy = max(max_bomb_enemy, c)
return max_bomb_enemy
```

**Optimized Solution**

- We can perform an optimization: we can create a 2D array. For row wise direction, we can simply count the number of enemies between two walls, and then each value between 2 walls will be increased by the count of the enemies. A similar thing can be done column wise.
- Check this image: https://goo.gl/photos/s8cS5p3zLjawXJkM8. The code simply implements this.

```
class Solution(object):
def process_left_right(self, i, grid, value):
cnt, N, M = 0, len(grid), len(grid[0])
for j in range(M):
if grid[i][j] == "W":
cnt = 0
elif grid[i][j] == "E":
cnt += 1
else:
value[i][j] += cnt
return
def process_right_left(self, i, grid, value):
cnt, N, M = 0, len(grid), len(grid[0])
for j in range(M-1, -1, -1):
if grid[i][j] == "W":
cnt = 0
elif grid[i][j] == "E":
cnt += 1
else:
value[i][j] += cnt
return
def process_up_down(self, j, grid, value):
cnt, N, M = 0, len(grid), len(grid[0])
for i in range(N):
if grid[i][j] == "W":
cnt = 0
elif grid[i][j] == "E":
cnt += 1
else:
value[i][j] += cnt
return
def process_down_up(self, j, grid, value):
cnt, N, M = 0, len(grid), len(grid[0])
for i in range(N-1, -1, -1):
if grid[i][j] == "W":
cnt = 0
elif grid[i][j] == "E":
cnt += 1
else:
value[i][j] += cnt
return
def maxKilledEnemies(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid == []:
return 0
N, M = len(grid), len(grid[0])
value = [[0]*M for _ in range(N)]
self.max_bomb_enemy = 0
for i in range(N):
self.process_left_right(i, grid, value)
self.process_right_left(i, grid, value)
for j in range(M):
self.process_up_down(j, grid, value)
self.process_down_up(j, grid, value)
for i in range(N):
if value[i]:
self.max_bomb_enemy = max(self.max_bomb_enemy, max(value[i]))
return self.max_bomb_enemy
```