LeetCode 361. 轰炸敌人

2021-03-12 HGNULB 约 7 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 361. 轰炸敌人

题意分析

给一个由 'W'（墙）、'E'（敌人）、'0'（空地）组成的二维网格。要在某个空地上放一颗炸弹，它会沿着同一行和同一列向四个方向扩散，杀死路径上的敌人，但遇到墙就停止（墙不会被摧毁，也挡住后面的敌人）。求能杀死的敌人数的最大值。

先把规则翻译成可计算的形式。在格子 $(r, c)$ 放炸弹的收益，等于「该格所在行段内的敌人数」加上「该格所在列段内的敌人数」。这里的「行段」指的是：从 $(r, c)$ 出发向左右各延伸，直到碰到墙或网格边界为止的那一段连续区域；「列段」同理。注意炸弹放在空地上，所以格子本身不是敌人，不会被重复计入。

「墙阻断爆炸」这条规则带来的结构性质是本题的题眼：每一行被墙切成若干互不影响的连续段，同一段内的任何一个格子，其「行方向能炸到的敌人数」完全相同。列同理。换句话说，收益不是逐格独立的，而是「行段属性 + 列段属性」的组合。

这个性质直接指向优化方向。朴素做法要为每个空地向四方向各扫一遍，同一段里的格子把相同的统计重复做了 $O(\text{段长})$ 次。设网格是 $m \times n$，最坏是 $O(mn(m+n))$。而如果每段只统计一次、段内共享结果，就能降到 $O(mn)$。

还有一处细节：答案位置必须是空地。敌人格和墙格即使算出来的行段列段之和很大，也不能作为候选。这是最容易在写完主逻辑后遗漏的一条约束。

边界：网格为空或第一行为空时返回 0；全是墙时没有空地，答案是 0；只有一个空地且周围没有敌人时答案是 0；空地上放炸弹但同行同列一个敌人都没有，收益是 0 而不是无效。

解法：动态规划状态转移

核心思路

墙把每一行、每一列切成若干独立线段。同一行段内任意空地能击中的横向敌人数相同；同一列段也一样。与其从每个空地向四周重复扫描，不如只在线段起点统计一次并复用。

按行遍历时维护：

rowHits：当前格所在行段的敌人数；

colHits[col]：当前格所在第 col 列段的敌人数。

当前格在行首或左边是墙时，重新向右统计 rowHits；在首行或上方是墙时，重新向下统计对应 colHits。只有当前格是空地 '0' 时，才用两者之和更新答案。

正确性说明：扫描不变量是，处理格子 (row,col) 时，rowHits 与 colHits[col] 分别精确等于该格所在行段、列段中的敌人总数。进入新段时完整重算，段内则复用同一值，因此不变量成立。墙阻断两段，横纵敌人集合不会重叠，空地收益就是两者之和；对所有空地取最大值即为答案。

每个行段只被横向扫描一次，每个列段只被纵向扫描一次，所以所有重算的总长度仍是矩阵大小。

解题步骤

空网格直接返回 0。

创建长度为列数的 colHits，并初始化 rowHits=0。

按行遍历每个格子；遇到行段或列段起点时重新统计对应段。

当前格为 '0' 时，用 rowHits+colHits[col] 更新最大值。

返回答案。

样例网格 [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]] 在中心空地可炸 3 个敌人。全是敌人或墙而没有空地时，答案保持 0；墙两侧的敌人属于不同段，不能互相计入。

代码实现

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
}

复杂度分析

设网格为 m*n。

时间复杂度： $O(mn)$。主循环访问每格一次，所有行段和列段扫描总长度各为 $mn$。

空间复杂度： $O(n)$，仅保存每列当前段的敌人数。

关键点总结

墙把问题切成行段和列段，段内所有空地共享同一方向统计。

行优先遍历只需一个 rowHits，但各列状态同时存在，需要 colHits 数组。

段起点是边界或前一个位置为墙；只有这时才重算。

炸弹只能放在空地，敌人和墙上的统计值不能参与答案。

分段复用把重复四向扫描降为线性时间，并只需一行额外状态。

易错点总结

在敌人或墙上更新答案： 没有合法空地时应返回 0。

用一个标量保存所有列统计： 不同列的当前段会互相覆盖。

遇到墙本身才重算： 新段起点是墙后的第一个格子。

扫描段时不在墙处停止： 会把墙另一侧敌人错误计入。

漏掉首行或首列起点： 对应方向状态从未初始化。

相似题目

题目	难度	考察点
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和的标准载体，对照理解「预处理矩阵」与本题「滚动缓存」的空间取舍
1314. 矩阵区域和	中等	每格答案来自一个固定半径的子矩阵和，同样靠预处理消除重复统计
42. 接雨水	困难	每个位置的收益由左右两侧的最值决定，考察「双向预处理」到「双指针」的优化
238. 除了自身以外数组的乘积	中等	前缀积配后缀积，练习把「每个位置向两侧扫描」降成两趟线性递推
221. 最大正方形	中等	状态定义在「以当前格为右下角」上，考察二维 dp 的转移设计
85. 最大矩形	困难	逐行维护高度数组再套单调栈，同为「按行滚动维护列状态」的思路
84. 柱状图中最大的矩形	困难	每根柱子向两侧扩展到边界，用单调栈把 $O(n^2)$ 的扩展降到 $O(n)$