Problem statement

https://leetcode.com/problems/bomb-enemy/

Solution

There is straightforward $O(mn(m+n))$ solution, where we check full column and row. There is also DP solution, where in dp[i][j] we keep 4 numbers: number of enemies will be killed at top, down, left and right, if we put bomb in current cell. Be careful, if we want top, we need to start from bottom row. So, good idea is to add border with walls to our grid and then traverse it in $4$ different directions, see Problem 0764. Largest Plus Sign, where we use similar idea.

Complexity

Time complexity is $O(mn)$, space complexity is $O(mn)$ as well.

Code

class Solution:
    def maxKilledEnemies(self, grid):
        m, n, ans = len(grid), len(grid[0]), 0

        bordered = [["W"] * (n+2) for _ in range(m+2)]
        for i, j in product(range(m), range(n)):
            bordered[i+1][j+1] = grid[i][j]

        dp = [[[0] * 4 for _ in range(n+2)] for _ in range(m+2)]
        
        for dx, dy, dr in [(-1,0,0),(1,0,1),(0,-1,2),(0,1,3)]:
            for x in range(1, m+1)[::(-dx>=0)*2-1]:
                for y in range(1, n+1)[::(-dy>=0)*2-1]:
                    if bordered[x][y] == "W": continue
                    dp[x][y][dr] = dp[x+dx][y+dy][dr] + int(bordered[x][y] == "E")
                    
                    
        for i, j in product(range(1, m+1), range(1, n+1)):
            if bordered[i][j] == "0":
                ans = max(ans, sum(dp[i][j]))

        return ans