坐标型动态规划——轰炸敌人

本是古典何须时尚 2022-10-27 06:25 144阅读 0赞

想象一下炸弹人游戏，在你面前有一个二维的网格来表示地图，网格中的格子分别被以下三种符号占据：

‘W’ 表示一堵墙  
‘E’ 表示一个敌人  
‘0’（数字 0）表示一个空位  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

请你计算一个炸弹**最多能炸多少敌人**。（最值类型）

由于炸弹的威力不足以穿透墙体，炸弹只能炸到同一行和同一列没被墙体挡住的敌人。

注意：你只能把炸弹放在一个空的格子里

示例:

输入: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
    输出: 3 
    解释: 对于如下网格
    
    0 E 0 0 
    E 0 W E 
    0 E 0 0

假如在位置 (1,1) 放置炸弹的话，可以炸到 3 个敌人

### 1、题目分析 ###

这个题目复杂的地方在于，这个炸弹的可以往四个方向传播，并且传播路径上可能会遇到墙阻碍。所以这里我们需要拆解一下问题。其实我们只需要计算一个方向上面，然后剩下的几个方向也是类似的，所以我们只在一个方向上进行分析。后面的分析我们选择向上的方向。

### 2、确定状态 ###

这里的最后一步我的理解就是炸弹的最终位置放在什么地方。

假设在（i，j）格放一个炸弹，它向上炸死的敌人数分为三种情况：

*  （i，j）格为空地：（i-1，j）格向上能炸死的敌人数
 *  （i，j）格为空地：（i-1，j）格向上能炸死的敌人数+1
 *  （i，j）格为墙：0

可以发现当我们需要求（i，j）的时候，需要知道（i-1，j）的情况，这满足子问题要求。

### 3、转移方程 ###

假设Up\[i\]\[j\]表示(i,j)格放一个炸弹向上能炸死的敌人数  
![在这里插入图片描述][20210203214344968.png]

### 4、初始条件和边界情况 ###

初始条件：第0行的值和格子里面的内容相关。

*  Up\[i\]\[j\]=0，如果(0,j)格不是敌人
 *  \[Up\[i\]\[j\]=1，如果(0,j)格是敌人

边界情况：注意保证下标要保证大于0小于行列数

### 5、计算顺序 ###

按照行，逐行计算。  
时间复杂度：O(MN)；空间复杂度：O(MN)

### 6、代码实现 ###

上面只解释了向上传播的情况。其他方向的实现类似。

#主要收获就是从四个方向分析的动态规划，申请了四个数组去考虑
    class Solution:
        def maxKilledEnemies(self, grid):
            """ :type grid: List[List[str]] :rtype: int """
            if len(grid)==0 or len(grid[0])==0:
                return 0
            up = [[0]*len(grid[0]) for i in range(len(grid))]
            down = [[0] * len(grid[0]) for i in range(len(grid))]
            right = [[0] * len(grid[0]) for i in range(len(grid))]
            left = [[0] * len(grid[0]) for i in range(len(grid))]
    
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if i>0:
                        if grid[i][j]=='E':
                            up[i][j]=up[i-1][j]+1
                        if grid[i][j]=='0':
                            up[i][j]=up[i-1][j]
                    elif grid[i][j]=='E' and i==0:
                            up[i][j]=1
            for i in range(len(grid)-1,-1,-1):
                for j in range(len(grid[0])):
                    if i<len(grid)-1:
                        if grid[i][j]=='E':
                            down[i][j]=down[i+1][j]+1
                        if grid[i][j]=='0':
                            down[i][j]=down[i+1][j]
                    elif grid[i][j]=='E' and i==len(grid)-1:
                            down[i][j]=1
            for j in range(len(grid[0])):
                for i in range(len(grid)):
                    if j>0:
                        if grid[i][j]=='E':
                            left[i][j]=left[i][j-1]+1
                        if grid[i][j]=='0':
                            left[i][j]=left[i][j-1]
                    elif grid[i][j]=='E' and j==0:
                            left[i][j]=1
            for j in range(len(grid[0])-1,-1,-1):
                for i in range(len(grid)):
                    if j<len(grid[0])-1:
                        if grid[i][j]=='E':
                            right[i][j]=right[i][j+1]+1
                        if grid[i][j]=='0':
                            right[i][j]=right[i][j+1]
                    elif grid[i][j]=='E' and j==len(grid[0])-1:
                            right[i][j]=1
            max1=0
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j]=='0':
                        max1=max(max1,up[i][j]+down[i][j]+right[i][j]+left[i][j])
            return max1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/3f12ab06eb96473daca89aa512e7b77e.png
[20210203214344968.png]: /images/20221024/f0aeb4ee4374410f9db239febef94a8c.png