Question

361. 轰炸敌人

English Version

题目描述

给你一个大小为 m x n 的矩阵 grid ，其中每个单元格都放置有一个字符：

• 'W' 表示一堵墙
• 'E' 表示一个敌人
• '0'（数字 0）表示一个空位

返回你使用 一颗炸弹 可以击杀的最大敌人数目。你只能把炸弹放在一个空位里。

由于炸弹的威力不足以穿透墙体，炸弹只能击杀同一行和同一列没被墙体挡住的敌人。

 

示例 1：

输入：grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
输出：3

示例 2：

输入：grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
输出：1

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] 可以是 'W'、'E' 或 '0'

解法

方法一

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 {
  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;
  }
}

class Solution {
public:
  int maxKilledEnemies(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> g(m, vector<int>(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 = max(ans, g[i][j]);
      }
    }
    return ans;
  }
};

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
}