Problem description:

Given an m x n matrix grid where each cell is either a wall 'W', an enemy 'E' or empty '0', return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.

Example 1:

https://assets.leetcode.com/uploads/2021/03/27/bomb1-grid.jpg

1
2
Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

Example 2:

https://assets.leetcode.com/uploads/2021/03/27/bomb2-grid.jpg

1
2
Input: grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
Output: 1

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] is either 'W', 'E', or '0'.

Solution:

Traverse left to right, top to bottom

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        dp = [[0]* len(grid[0])]*len(grid)
        def kills(grid, i, j):
            # go up 
            res = 0
            tm, dm = i-1, i+1
            while 0 <= tm:
                if grid[tm][j] == "E":
                    res += 1
                if grid[tm][j] == "W":
                    break
                tm -= 1
            while dm < len(grid):
                if grid[dm][j] == "E":
                    res += 1
                if grid[dm][j] == "W":
                    break
                dm += 1
            tn, dn = j-1, j+1
            while 0 <= tn:
                if grid[i][tn] == "E":
                    res += 1
                if grid[i][tn] == "W":
                    break
                tn -= 1
            while dn < len(grid[0]):
                if grid[i][dn] == "E":
                    res += 1
                if grid[i][dn] == "W":
                    break
                dn += 1
            return res
        
        res = float('-inf')
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '0':
                    dp[i][j] = kills(grid, i, j)
                    res = max(res, dp[i][j])
        return res if res != float('-inf') else 0

time complexity: $O(mn)$
space complexity: $O(mn)$
reference:
related problem: