LeetCode 361. 轰炸敌人

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 361. 轰炸敌人

思路分析

解法一：动态规划（推荐）

核心思路：

对矩阵中每个空地，统计放置炸弹能炸到的敌人总数，取最大值

朴素做法对每个空地四方向遍历，时间复杂度 O(m²n + mn²)

优化：行方向预计算 rowHits[j] 表示当前行从 j 出发向右能炸到的敌人数，遇到墙壁才重新计算；列方向预计算 colHits[i] 类似

遍历到空地时，直接查表得到四方向总数，整体降至 O(mn)

复杂度分析：

时间复杂度：O(mn)，其中 m、n 分别表示矩阵行数和列数

空间复杂度：O(mn)，用于存储列方向的预计算数组

class Solution {

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

    int m = grid.length;
    int n = grid[0].length;
    int result = 0;

    // colHits[j] 表示第 j 列当前段能炸到的敌人数
    int[] colHits = new int[n];
    int rowHits = 0;

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // 遇到墙或列起点时，重新计算行方向能炸到的敌人数
        if (j == 0 || grid[i][j - 1] == 'W') {
          rowHits = 0;
          for (int k = j; k < n && grid[i][k] != 'W'; k++) {
            if (grid[i][k] == 'E') {
              rowHits++;
            }
          }
        }

        // 遇到墙或行起点时，重新计算列方向能炸到的敌人数
        if (i == 0 || grid[i - 1][j] == 'W') {
          colHits[j] = 0;
          for (int k = i; k < m && grid[k][j] != 'W'; k++) {
            if (grid[k][j] == 'E') {
              colHits[j]++;
            }
          }
        }

        // 当前位置为空地时，统计总炸到数
        if (grid[i][j] == '0') {
          result = Math.max(result, rowHits + colHits[j]);
        }
      }
    }

    return result;
  }
}

func maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    m, n := len(grid), len(grid[0])
    result := 0

    // colHits[j] 表示第 j 列当前段能炸到的敌人数
    colHits := make([]int, n)
    rowHits := 0

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            // 遇到墙或列起点时，重新计算行方向
            if j == 0 || grid[i][j-1] == 'W' {
                rowHits = 0
                for k := j; k < n && grid[i][k] != 'W'; k++ {
                    if grid[i][k] == 'E' {
                        rowHits++
                    }
                }
            }

            // 遇到墙或行起点时，重新计算列方向
            if i == 0 || grid[i-1][j] == 'W' {
                colHits[j] = 0
                for k := i; k < m && grid[k][j] != 'W'; k++ {
                    if grid[k][j] == 'E' {
                        colHits[j]++
                    }
                }
            }

            // 当前位置为空地时更新结果
            if grid[i][j] == '0' {
                if total := rowHits + colHits[j]; total > result {
                    result = total
                }
            }
        }
    }

    return result
}

相似题目

题目	难度	考察点
73. 矩阵置零	中等	矩阵、模拟
54. 螺旋矩阵	中等	矩阵模拟
221. 最大正方形	中等	动态规划、矩阵
85. 最大矩形	困难	动态规划、栈
62. 不同路径	中等	动态规划、矩阵
240. 搜索二维矩阵 II	中等	矩阵、二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/16485878