- Lonely Pixel I
- Review: Dynamic Programming Problems
- Review: Game Problems
- Tag: #dynamicprogramming, #game
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)
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) 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] else: k = 1 if ch == 'E' else 0 dp[i][j] = [dp[i-1][j]+k if i>0 else k, \ dp[i][j-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] = dp[i+1][j]+k if i<row_count-1 else k dp[i][j] = dp[i][j+1]+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