361.md

• time: O(mn)
• space: O(mn)
• 400ms
• 75%

class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        m = len(grid)
        if not m: return 0
        n = len(grid[0])

        boom = [[0]*n for _ in range(m)]

        for r in range(m):
            pre = 0
            # left -> right
            for c in range(n):
                if grid[r][c] == "W": pre = 0
                elif grid[r][c] == "E": pre += 1
                boom[r][c] += pre
            # right -> left
            pre = 0
            for c in range(n-1, -1, -1):
                if grid[r][c] == "W": pre = 0
                elif grid[r][c] == "E": pre += 1
                boom[r][c] += pre
        for c in range(n):
            # up -> down
            pre = 0
            for r in range(m):
                if grid[r][c] == "W": pre = 0
                elif grid[r][c] == "E": pre += 1
                boom[r][c] += pre
            # down -> up
            pre = 0
            for r in range(m-1, -1, -1):
                if grid[r][c] == "W": pre = 0
                elif grid[r][c] == "E": pre += 1
                boom[r][c] += pre
        ans = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c]=="0":
                    ans = max(ans, boom[r][c])
        return ans