华为 · 广度优先搜索(BFS) · 算法编程题
华为 广度优先搜索(BFS) N ≤ 300 时限 3 秒 / 256 MB

题目描述

在遥远的未来，人类的星际方舟“启示录号”在穿越一片未知的小行星带时，船体遭到了微型陨石的撞击，导致部分区域受损。
为了评估飞船的结构完整性，维修系统需要对一块大小为 N × M 的船体截面进行扫描。
扫描结果被表示为一个 N × M 的矩阵，其中每个元素代表一个船体单元的状态：
0 ：表示该单元完好无损。
1 ：表示该单元已损坏或出现破裂。
一个“独立密封舱”被定义为一片由一个或多个相连的完好单元组成的区域，该区域在上下左右四个方向上被损坏单元完全包围。
一个重要的前提是：扫描矩阵的外部区域被认为是与飞船主体相连的、广阔的完好区域 。
因此，任何与矩阵边界直接或间接相连的完好单元区域，都被视作飞船主体结构的一部分，而不是“独立密封舱”。
您的任务是编写一个程序，计算出所有独立密封舱的总面积（即，其中包含的完好单元的总数）。

输入输出

输入描述
第一行包含两个整数 M 和 N ，分别代表船体截面扫描图的宽度和高度。
1 ≤ M, N ≤ 300
接下来的 N 行，每行包含 M 个整数（ 0 或 1 ），代表扫描矩阵的每一行。
输出描述
输出一个整数，代表所有独立密封舱的总面积。

样例共 3 组

样例 1
输入
7 7
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
1 0 1 0 1 0 1
1 0 1 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
输出
17
样例 2
输入
8 4
1 1 1 0 1 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 1 1 1
0 0 1 0 0 1 1 1
输出
2
样例 3
输入
8 4
0 0 1 0 1 0 0 0
0 0 1 0 0 1 0 0
1 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0
输出
0

算法解析依据充分

考点：广度优先搜索(BFS)

数据规模 N ≤ 300 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：M ≤ 300，N ≤ 300
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：广度优先搜索(BFS)

本题切入点

网格洪水填充：从边界出发把与外部连通的 0 全部标记为「非密封」，剩余未被标记的 0 才属于独立密封舱，统计其个数即可。

按层扩散搜索，无权图上第一次到达即最短路。

思路框架（广度优先搜索(BFS) 通法 · 非本题专属）

  1. 起点入队并标记已访问。
  2. 每次取队首，把它的所有未访问邻居入队并记录步数。
  3. 第一次访问到目标时，步数即为最少步数。
  4. 网格类题目通常有 4（或 8）个方向，用方向数组统一处理。

实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。

复杂度：时间 O(V+E) ｜ 空间 O(V)

该范式的通法易错点

  • 出队才标记访问导致 MLE/TLE。
  • 网格边界没判，越界访问。
  • 多源 BFS 时只把第一个起点入队。

对照本题

  • 数据规模 N ≤ 300，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。

样例

样例 1

  • 输入：7 7 / 1 1 1 1 1 1 1 / 1 0 0 0 0 0 1 / 1 0 1 1 1 0 1 / 1 0 1 0 1 0 1 / 1 0 1 1 1 0 1 / 1 0 0 0 0 0 1 / 1 1 1 1 1 1 1
  • 输出：17

样例 2

  • 输入：8 4 / 1 1 1 0 1 1 1 1 / 1 0 1 0 1 1 0 1 / 1 1 1 0 1 1 1 1 / 0 0 1 0 0 1 1 1
  • 输出：2

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-11月19号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解