轰炸敌人

Submission

运行时间: 184 ms

内存: 42.7 MB

class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:

        rows = len(grid)
        cols = len(grid[0])

        dprow = [[0]* cols for _ in range(rows)]
        dpcol = [[0]* cols for _ in range(rows)]

        for i in range(rows):
            curnum = 0
            for j in range(cols):
                if grid[i][j] == 'E':
                    curnum += 1
                elif grid[i][j] == 'W':
                    curnum = 0
                dprow[i][j] = curnum

            curmax = curnum
            for j in range(cols-1, -1, -1):    
                if grid[i][j] == 'W':
                    curmax = 0
                elif grid[i][j] == 'E':
                    if dprow[i][j] > curmax:
                        curmax = dprow[i][j]
                    dprow[i][j] = 0
                else:
                    if dprow[i][j] > curmax:
                        curmax = dprow[i][j]
                    dprow[i][j] = curmax

        for j in range(cols):
            curnum = 0
            for i in range(rows):
                if grid[i][j] == 'E':
                    curnum += 1
                elif grid[i][j] == 'W':
                    curnum = 0
                dpcol[i][j] = curnum

            curmax = curnum
            for i in range(rows-1, -1, -1):    
                if grid[i][j] == 'W':
                    curmax = 0
                elif grid[i][j] == 'E':
                    if dpcol[i][j] > curmax:
                        curmax = dpcol[i][j]
                    dpcol[i][j] = 0
                else:
                    if dpcol[i][j] > curmax:
                        curmax = dpcol[i][j]
                    dpcol[i][j] = curmax

        #print(dprow)
        #print(dpcol)
        globalmax = 0
        for i in range(rows):
            for j in range(cols):
                curdeath = dprow[i][j] + dpcol[i][j]
                if curdeath > globalmax:
                    globalmax = curdeath
        
        return globalmax

Explain

这个题解的思路是使用两个动态规划数组 dprow 和 dpcol 分别记录每个空格左边和上边的敌人数量。首先，遍历每一行，用 dprow 数组记录当前行每个空格左边的敌人数量。接着从右到左再次遍历该行，更新 dprow 数组，使其记录每个空格左右两侧的最大敌人数量。然后，用类似的方法遍历每一列，用 dpcol 数组记录每个空格上下两侧的最大敌人数量。最后，遍历整个网格，将每个空格在 dprow 和 dpcol 中对应的值相加，得到该空格所能消灭的敌人总数，并更新全局最大值。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:

        rows = len(grid)
        cols = len(grid[0])
        
        # 初始化 dprow 和 dpcol 数组
        dprow = [[0]* cols for _ in range(rows)]
        dpcol = [[0]* cols for _ in range(rows)]

        # 遍历每一行
        for i in range(rows):
            curnum = 0
            # 从左到右遍历
            for j in range(cols):
                if grid[i][j] == 'E':
                    curnum += 1
                elif grid[i][j] == 'W':
                    curnum = 0
                dprow[i][j] = curnum
            
            curmax = curnum
            # 从右到左遍历
            for j in range(cols-1, -1, -1):    
                if grid[i][j] == 'W':
                    curmax = 0
                elif grid[i][j] == 'E':
                    if dprow[i][j] > curmax:
                        curmax = dprow[i][j]
                    dprow[i][j] = 0
                else:
                    if dprow[i][j] > curmax:
                        curmax = dprow[i][j]
                    dprow[i][j] = curmax

        # 遍历每一列
        for j in range(cols):
            curnum = 0
            # 从上到下遍历
            for i in range(rows):
                if grid[i][j] == 'E':
                    curnum += 1
                elif grid[i][j] == 'W':
                    curnum = 0
                dpcol[i][j] = curnum
            
            curmax = curnum
            # 从下到上遍历
            for i in range(rows-1, -1, -1):    
                if grid[i][j] == 'W':
                    curmax = 0
                elif grid[i][j] == 'E':
                    if dpcol[i][j] > curmax:
                        curmax = dpcol[i][j]
                    dpcol[i][j] = 0
                else:
                    if dpcol[i][j] > curmax:
                        curmax = dpcol[i][j]
                    dpcol[i][j] = curmax
        
        # 遍历网格，找到最大消灭敌人数
        globalmax = 0
        for i in range(rows):
            for j in range(cols):
                curdeath = dprow[i][j] + dpcol[i][j]
                if curdeath > globalmax:
                    globalmax = curdeath
        
        return globalmax

Explore

在处理每一行和每一列时，需要从两个方向进行遍历，以确保能够正确计算出每个空格可以影响到的敌人的总数。从左到右或从上到下的遍历仅能统计出来自一个方向的敌人数，而从右到左或从下到上的遍历则可以补充另一个方向的敌人数。这样，每个位置上存储的数字最终表示的是两边所有可直接攻击到的敌人的总和，确保了计算的全面性。

在从右到左遍历时，dprow[i][j] 设置为 0 当 grid[i][j] == 'E' 是因为敌人本身不能被算作可以攻击的敌人数量。此处设置为 0 的目的是防止其自身被计算在内。这不会导致计算错误，反而是为了确保不将当前位置的敌人也算作可攻击的敌人。每个敌人都只在其被首次遇到时计数，之后即使在同一行或列中再次遇到也应重置计数器，以避免重复计数。

在更新 dprow 和 dpcol 数组时，通过在遇到墙（'W'）时重置当前计数（设置为 0），确保每段连续的空地只统计到该段中的敌人。此外，在从一个方向开始遍历时，每次更新只基于当前方向的统计，当方向改变时，重置统计，这样可以避免重复计算同一行或同一列中的敌人数目。

在计算每个空格能消灭的敌人总数时，直接将 dprow 和 dpcol 对应的值相加是可行的，因为这两个数组分别统计了在不考虑墙阻挡时，从行和列两个维度可以攻击到的敌人数。每个数组的更新过程中已经考虑到了墙的阻挡效果，即每次遇到墙时，计数会被重置。因此，这两个数组的值加起来即表示在没有墙阻挡的情况下，该点潜在能够攻击到的敌人总数。