Leetcode: Bomb Enemy

Bomb Enemy

Similar Problems:

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 that you can only put the bomb at an empty cell.


For the given grid

0 E 0 0
E 0 W E
0 E 0 0

return 3. (Placing a bomb at (1,1) kills 3 enemies)

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/bomb-enemy
## Basic Ideas: dynamic programming
## dp[i][j] = [x1, y1, x2, y2]
##  x1: from top to current row
##      How many enemies boom[i][j] can kill
##  y1: from left to current column
##  x2: from bottom to current row
##  y2: from right to current column
## Assumption: if we place a boom in 'W', we will kill no enemies
## Complexity: Time O(m*n), Space O(m*n)
class Solution:
    def maxKilledEnemies(self, grid):
        :type grid: List[List[str]]
        :rtype: int
        row_count = len(grid)
        if row_count == 0: return 0
        col_count = len(grid[0])

        dp = [[[0, 0, 0, 0] for j in range(col_count)] for i in range(row_count)]

        # caculate: x1, y1. 
        for i in range(row_count):
            for j in range(col_count):
                ch = grid[i][j]
                if ch == 'W':
                    dp[i][j] = [0, 0, 0, 0]
                    k = 1 if ch == 'E' else 0
                    dp[i][j] = [dp[i-1][j][0]+k if i>0 else k, \
                                dp[i][j-1][1]+k if j>0 else k, \
                                k, k]

        max_count = 0
        # caculate: x2, y2, and get the result
        for i in range(row_count-1, -1, -1):
            for j in range(col_count-1, -1, -1):
                ch = grid[i][j]
                if ch == 'W': continue
                k = 1 if ch == 'E' else 0
                dp[i][j][2] = dp[i+1][j][2]+k if i<row_count-1 else k
                dp[i][j][3] = dp[i][j+1][3]+k if j<col_count-1 else k
                # get result
                if grid[i][j] == '0':
                    max_count = max(max_count, sum(dp[i][j]))

        return max_count

Share It, If You Like It.

Leave a Reply

Your email address will not be published.