LeetCode: 361. 轰炸敌人¶

1、题目描述¶

• 'W' 表示一堵墙
• 'E' 表示一个敌人
• '0'（数字 0）表示一个空位

输入: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]

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



2、解题思路¶

• 动态规划

class Solution:
def maxKilledEnemies(self, grid: List[List[str]]) -> int:
if not grid:
return 0
row, col = len(grid), len(grid[0])
dp = [[[0, 0, 0, 0] for _ in range(col)] for _ in range(row)]

# 坐标验证
def available(m, n):
return 0 <= m < row and 0 <= n < col

#  [0, 0, 0, 0]
# 左 上 右 下

ans = 0

for i in range(row):
for j in range(col):
up = [i - 1, j]
left = [i, j - 1]
if grid[i][j] == "W":
continue
if available(*up):
dp[i][j][1] = dp[up[0]][up[1]][1]
if available(*left):
dp[i][j][0] = dp[left[0]][left[1]][0]
if grid[i][j] == "E":
dp[i][j][1] += 1
dp[i][j][0] += 1

for i in range(row - 1, -1, -1):
for j in range(col - 1, -1, -1):
if grid[i][j] == "W":
continue
right = [i, j + 1]
bottom = [i + 1, j]
if available(*right):
dp[i][j][2] = dp[right[0]][right[1]][2]
if available(*bottom):
dp[i][j][3] = dp[bottom[0]][bottom[1]][3]
if grid[i][j] == "E":
dp[i][j][2] += 1
dp[i][j][3] += 1
if grid[i][j] == "0":
ans = max(ans, sum(dp[i][j]))

return ans