Question

Formatted question description: https://leetcode.ca/all/361.html

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:

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

Example 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'.

Algorithm

Create four cumulative arrays v1, v2, v3, v4,

v1 is the cumulative array from left to right in the horizontal direction
v2 is the cumulative array from right to left in the horizontal direction
v3 is the cumulative array from top to bottom in the vertical direction
v4 is the cumulative array from bottom to top in the vertical direction

After building this cumulative array, for any position (i, j), the maximum number of enemies that can be killed is v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j], finally by comparing the cumulative sum of each position, you can get the result.

Code

public class Bomb_Enemy {

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int m = grid.length, n = grid[0].length, res = 0;

            int[][] v1 = new int[m][n];
            int[][] v2 = new int[m][n];
            int[][] v3 = new int[m][n];
            int[][] v4 = new int[m][n];

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) { // left to right
                    int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
                    v1[i][j] = grid[i][j] == 'E' ? t + 1 : t; // @note: 没有关系，i-j 是0才可以放，不会是E
                }
                for (int j = n - 1; j >= 0; --j) { // right to left
                    int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
                    v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
                }
            }
            for (int j = 0; j < n; ++j) {
                for (int i = 0; i < m; ++i) { // up to down
                    int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
                    v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
                }
                for (int i = m - 1; i >= 0; --i) { // down to up
                    int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
                    v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
                }
            }

            // final check
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '0') {
                        res = Math.max(res, v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]);
                    }
                }
            }
            return res;
        }
    }

    public class Solution_2d {
        public int maxKilledEnemies(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            /*
                 enemyCount[i][0] stores the position of a certain W in the ith row,
                 enemyCount[i][1] stores the number of E from the W identified by enemyCount[i][0] to the previous W,

                 Initialization: enemyCount[i][0] = -1, enemyCount[i][1] = 0
             */
            int[][] enemyCount = new int[grid.length][2];

            for (int i = 0; i < enemyCount.length; i++) {
                enemyCount[i][0] = -1;
            }

            int max = 0;
            for (int j = 0; j < grid[0].length; j++) {

                int colEnemy = countColEnemy(grid, j, 0);

                for (int i = 0; i < grid.length; i++) {
                    // If the current position is the first one or the previous one is a wall, start traversing backward from the current position,
                    // Traverse to [end] or [wall] and stop, count the number of enemies
                    if (grid[i][j] == '0') { // ok to put bomb
                        if (j > enemyCount[i][0]) { // already over 1st wall of this row
                            update(enemyCount, grid, i, j);
                        }
                        max = Math.max(colEnemy + enemyCount[i][1], max);
                    }
                    if (grid[i][j] == 'W') {
                        colEnemy = countColEnemy(grid, j, i + 1);
                    }
                }

            }

            return max;
        }

        private void update(int[][] enemyCount, char[][] grid, int i, int j) {
            int count = 0;
            int k = enemyCount[i][0] + 1;
            while (k < grid[0].length && (grid[i][k] != 'W' || k < j)) {
                if (grid[i][k] == 'E') {
                    count += 1;
                }
                if (grid[i][k] == 'W') {
                    count = 0;
                }
                k += 1;
            }
            enemyCount[i][0] = k;
            enemyCount[i][1] = count;
        }

        private int countColEnemy(char[][] grid, int j, int start) {
            int count = 0;
            int i = start;
            while (i < grid.length && grid[i][j] != 'W') { // until next wall
                if (grid[i][j] == 'E') {
                    count += 1;
                }
                i += 1;
            }
            return count;
        }
    }
}

############

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] g = new int[m][n];
        for (int i = 0; i < m; ++i) {
            int t = 0;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
            t = 0;
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
        }
        for (int j = 0; j < n; ++j) {
            int t = 0;
            for (int i = 0; i < m; ++i) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
            t = 0;
            for (int i = m - 1; i >= 0; --i) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') {
                    ans = Math.max(ans, g[i][j]);
                }
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/bomb-enemy/
// Time: O(MN(M+N))
// Space: O(1)
class Solution {
private:
    int M, N;
    int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
    int count(vector<vector<char>>& grid, int x, int y, int dir[2]) {
        int ans = 0;
        while (true) {
            x += dir[0];
            y += dir[1];
            if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] == 'W') break;
            if (grid[x][y] == 'E') ++ans;
        }
        return ans;
    }
    int count(vector<vector<char>>& grid, int x, int y) {
        int ans = 0;
        for (auto &dir : dirs) ans += count(grid, x, y, dir);
        return ans;
    }
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        M = grid.size();
        N = grid[0].size();
        int ans = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] != '0') continue;
                ans = max(ans, count(grid, i, j));
            }
        }
        return ans;
    }
};

class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        g = [[0] * n for _ in range(m)]
        for i in range(m):
            t = 0
            for j in range(n):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
            t = 0
            for j in range(n - 1, -1, -1):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
        for j in range(n):
            t = 0
            for i in range(m):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
            t = 0
            for i in range(m - 1, -1, -1):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
        return max(
            [g[i][j] for i in range(m) for j in range(n) if grid[i][j] == '0'],
            default=0,
        )

############

class Solution(object):
  def maxKilledEnemies(self, grid):
    """
    :type grid: List[List[str]]
    :rtype: int
    """
    if not grid:
      return 0
    dpRow = [[0] * (len(grid[0]) + 2) for _ in range(0, len(grid) + 2)]
    dpCol = [[0] * (len(grid[0]) + 2) for _ in range(0, len(grid) + 2)]

    for i in range(0, len(grid)):
      for j in range(0, len(grid[0])):
        dpRow[i + 1][j + 1] = dpRow[i + 1][j]
        dpCol[i + 1][j + 1] = dpCol[i][j + 1]
        if grid[i][j] == "W":
          dpRow[i + 1][j + 1] = 0
          dpCol[i + 1][j + 1] = 0
        if grid[i][j] == "E":
          dpRow[i + 1][j + 1] += 1
          dpCol[i + 1][j + 1] += 1

    maxKilled = 0
    for i in reversed(range(0, len(grid))):
      for j in reversed(range(0, len(grid[0]))):
        if grid[i][j] == "W":
          continue
        dpRow[i + 1][j + 1] = max(dpRow[i + 1][j + 1], dpRow[i + 1][j + 2])
        dpCol[i + 1][j + 1] = max(dpCol[i + 1][j + 1], dpCol[i + 2][j + 1])
        if grid[i][j] == "0":
          maxKilled = max(maxKilled, dpRow[i + 1][j + 1] + dpCol[i + 1][j + 1])
    return maxKilled

func maxKilledEnemies(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		t := 0
		for j := 0; j < n; j++ {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
		t = 0
		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
	}
	for j := 0; j < n; j++ {
		t := 0
		for i := 0; i < m; i++ {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
		t = 0
		for i := m - 1; i >= 0; i-- {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
	}
	ans := 0
	for i, row := range grid {
		for j, v := range row {
			if v == '0' && ans < g[i][j] {
				ans = g[i][j]
			}
		}
	}
	return ans
}

361 - Bomb Enemy

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions