Problem statement

https://binarysearch.com/problems/Bomber-Man-Sequel/

Solution

Equal to Leetcode 0361. Bomb Enemy.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(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] == 1: continue
                    dp[x][y][dr] = dp[x+dx][y+dy][dr] + int(bordered[x][y] == 2)
                    
                    
        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