飞船扫描

题目分析

飞船穿越小行星带时船体受损，给定一个 $H \times W$ 的矩阵，1 表示完好单元，0 表示损坏单元。"独立密封舱"是被损坏单元（0）在上下左右四个方向完全包围的连通损坏区域——换言之，与矩阵边界相连的 0 不算独立密封舱，只有被 1 完全封闭在内部的 0 区域才算。求所有独立密封舱的总面积（即被封闭的 0 的个数）。

思路

BFS 边界染色（Flood Fill）

这是经典的"被围绕的区域"问题。核心观察：与矩阵边界相连的 0 一定不是密封舱的一部分，因为它们可以通过边界"逃出去"。因此只需要区分哪些 0 与边界连通、哪些 0 被完全包围。

算法步骤：

从矩阵的四条边出发，找到所有值为 0 的边界格子，加入 BFS 队列
BFS 向四个方向扩展，将所有与边界连通的 0 标记为已访问（例如改为 -1）
BFS 结束后，矩阵中剩余的 0 就是被 1 完全包围的密封舱，统计个数即为答案

以样例 1 为例验证： 7x7 矩阵，外圈全是 1，第二圈全是 0，内部还有一个 3x3 的 1 环包围一个 0。边界上没有 0，所以 BFS 不会标记任何格子。最终所有 0 都是被封闭的：第二圈 16 个 0 + 中心 1 个 0 = 17，与预期输出一致。

复杂度

时间复杂度： $O(H \times W)$ ，每个格子最多被访问一次
空间复杂度： $O(H \times W)$ ，存储矩阵和 BFS 队列

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main() {
    int W, H;
    scanf("%d%d", &W, &H);
    vector<vector<int>> grid(H, vector<int>(W));
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            scanf("%d", &grid[i][j]);

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    queue<pair<int,int>> q;

    // 从边界出发，标记所有与边界连通的 0
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if ((i == 0 || i == H-1 || j == 0 || j == W-1) && grid[i][j] == 0) {
                grid[i][j] = -1;
                q.push({i, j});
            }

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] == 0) {
                grid[nx][ny] = -1;
                q.push({nx, ny});
            }
        }
    }

    // 统计剩余的 0（被封闭的密封舱）
    int ans = 0;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (grid[i][j] == 0)
                ans++;
    printf("%d\n", ans);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken(); int W = (int) in.nval;
        in.nextToken(); int H = (int) in.nval;
        int[][] grid = new int[H][W];
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++) {
                in.nextToken();
                grid[i][j] = (int) in.nval;
            }

        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                if ((i == 0 || i == H - 1 || j == 0 || j == W - 1) && grid[i][j] == 0) {
                    grid[i][j] = -1;
                    q.add(new int[]{i, j});
                }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d], ny = cur[1] + dy[d];
                if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] == 0) {
                    grid[nx][ny] = -1;
                    q.add(new int[]{nx, ny});
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                if (grid[i][j] == 0) ans++;
        System.out.println(ans);
    }
}

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    W = int(input_data[idx]); idx += 1
    H = int(input_data[idx]); idx += 1
    grid = []
    for i in range(H):
        row = []
        for j in range(W):
            row.append(int(input_data[idx])); idx += 1
        grid.append(row)

    q = deque()
    for i in range(H):
        for j in range(W):
            if (i == 0 or i == H - 1 or j == 0 or j == W - 1) and grid[i][j] == 0:
                grid[i][j] = -1
                q.append((i, j))

    while q:
        x, y = q.popleft()
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == 0:
                grid[nx][ny] = -1
                q.append((nx, ny))

    ans = sum(grid[i][j] == 0 for i in range(H) for j in range(W))
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [W, H] = lines[0].split(' ').map(Number);
    const grid = [];
    for (let i = 0; i < H; i++)
        grid.push(lines[i + 1].split(' ').map(Number));

    const dx = [0, 0, 1, -1];
    const dy = [1, -1, 0, 0];
    const q = [];
    let head = 0;

    for (let i = 0; i < H; i++)
        for (let j = 0; j < W; j++)
            if ((i === 0 || i === H - 1 || j === 0 || j === W - 1) && grid[i][j] === 0) {
                grid[i][j] = -1;
                q.push([i, j]);
            }

    while (head < q.length) {
        const [x, y] = q[head++];
        for (let d = 0; d < 4; d++) {
            const nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] === 0) {
                grid[nx][ny] = -1;
                q.push([nx, ny]);
            }
        }
    }

    let ans = 0;
    for (let i = 0; i < H; i++)
        for (let j = 0; j < W; j++)
            if (grid[i][j] === 0) ans++;
    console.log(ans);
});