LeetCode 361. 轰炸敌人

约 6 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 会员题 1-2 字节
标签
数组 动态规划 矩阵

题目描述

✅ 361. 轰炸敌人

题意分析

网格中 'E' 表示敌人，'W' 表示墙，'0' 表示空地。只能在一个空地放炸弹，爆炸沿同行、同列四个方向传播，到墙为止，求最多能消灭多少敌人。敌人不会阻挡继续传播，墙后面的敌人则不能计入。

解法：行列分段统计复用

核心思路

[!blue]

若对每个空地重新扫描四个方向，相邻空地会反复数到同一批敌人。墙把每一行、每一列切成若干无墙的连续段，同一行段内任意空地能看到的横向敌人完全相同，同一列段内的纵向敌人也完全相同，所以可以按段统计并复用。

代码按行从左到右遍历。到达行首，或当前格左侧是墙时，表示进入了一个新行段，从当前位置向右数到下一面墙，保存为 rowHits。随后在该行段内移动时直接复用它；虽然预先只向右扫描，但起点是整段最左端，所以这个数包含当前候选位置左右两侧的全部敌人。

纵向同理：位于首行，或上方是墙时，从当前位置向下统计整个新列段，保存到 colHits[col]。以后扫描到同一列段的更低位置时，这个数同时包含其上方、下方的敌人。按行遍历会交替访问不同列，所以必须为每列分别保存状态，不能只用一个纵向计数。

当当前格为 '0' 时，rowHits + colHits[col] 就是放炸弹能消灭的数量。行段和列段只有当前格这一个交点，而它是空地，不是敌人，因此相加不会重复计数。墙或敌人位置都不能放炸弹，不能用它们更新答案；墙处暂时保留什么段计数也不会成为答案，离开墙进入新段时会重新计算。

每个无墙行段只在左端扫描一次，每个无墙列段只在顶端扫描一次。因此所有向右扫描的总长度为 $O(mn)$，所有向下扫描的总长度也为 $O(mn)$，不会因为辅助循环而重复扫描每个候选的整行整列。遍历所有空地取最大值；没有合法空地时，初始答案 $0$ 保持不变。

解题步骤

  1. 初始化列段计数数组。
  2. 行首或左侧为墙时重算当前行段。
  3. 首行或上方为墙时重算对应列段。
  4. 只在空地比较 rowHits+colHits[col]，取最大值。

代码实现

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

        int rows = grid.length;
        int cols = grid[0].length;
        int[] colHits = new int[cols];
        int rowHits = 0;
        int answer = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (col == 0 || grid[row][col - 1] == 'W') {
                    // 进入新行段时统计一次，段内其他格子复用。
                    rowHits = countRow(grid, row, col);
                }

                if (row == 0 || grid[row - 1][col] == 'W') {
                    // 每列分别保存当前无墙段的敌人数。
                    colHits[col] = countColumn(grid, row, col);
                }

                if (grid[row][col] == '0') {
                    answer = Math.max(answer, rowHits + colHits[col]);
                }
            }
        }

        return answer;
    }

    private int countRow(char[][] grid, int row, int start) {
        int enemies = 0;

        for (int col = start; col < grid[row].length && grid[row][col] != 'W'; col++) {
            if (grid[row][col] == 'E') {
                enemies++;
            }
        }

        return enemies;
    }

    private int countColumn(char[][] grid, int start, int col) {
        int enemies = 0;

        for (int row = start; row < grid.length && grid[row][col] != 'W'; row++) {
            if (grid[row][col] == 'E') {
                enemies++;
            }
        }

        return enemies;
    }
}

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

    rows, cols := len(grid), len(grid[0])
    colHits := make([]int, cols)
    rowHits := 0
    answer := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if col == 0 || grid[row][col-1] == 'W' {
                // 进入新行段时统计一次，段内其他格子复用。
                rowHits = countRow(grid, row, col)
            }
            if row == 0 || grid[row-1][col] == 'W' {
                // 每列分别保存当前无墙段的敌人数。
                colHits[col] = countColumn(grid, row, col)
            }
            if grid[row][col] == '0' &&
                rowHits+colHits[col] > answer {
                answer = rowHits + colHits[col]
            }
        }
    }
    return answer
}

func countRow(grid [][]byte, row int, start int) int {
    enemies := 0
    for col := start; col < len(grid[row]) && grid[row][col] != 'W'; col++ {
        if grid[row][col] == 'E' {
            enemies++
        }
    }
    return enemies
}

func countColumn(grid [][]byte, start int, col int) int {
    enemies := 0
    for row := start; row < len(grid) && grid[row][col] != 'W'; row++ {
        if grid[row][col] == 'E' {
            enemies++
        }
    }
    return enemies
}

复杂度分析

  • 时间复杂度：$O(mn)$，全部行段与列段的扫描总长度均为线性。
  • 空间复杂度：$O(n)$，保存每列当前段的敌人数。

关键点总结

[!green]

  • 按段统计、段内复用，避免每个空地重新扫描四方。
  • 行优先时只需一个行计数，但每列都需保留独立状态。
  • 只有空地可以作为答案候选。

易错点总结

[!yellow]

  • 在敌人或墙处更新答案：这些格子不能放炸弹。
  • 扫描越过墙：把无法击中的敌人算入。
  • 所有列共用一个计数：不同列段互相覆盖。
  • 漏掉首行或首列初始化：对应方向从未统计。

相似题目

题目 难度 关联与区别
1267. 统计参与通信的服务器 中等 同样按同行同列累计影响，原题没有墙，本题每行每列被墙分成独立可见区段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/16485878
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！