题解 | #飞船扫描#

题目链接

飞船扫描

题目描述

在遥远的未来，人类的星际方舟“启示录号”在穿越一片未知的小行星带时，船体遭到了微型陨石的撞击，导致部分区域受损。为了评估飞船的结构完整性，维修系统需要对一块大小为 $M \times N$ 的船体截面进行扫描。

扫描结果被表示为一个 $M \times N$ 的矩阵，其中每个元素代表一个船体单元的状态：

0：表示该单元完好无损。
1：表示该单元已损坏或出现破裂。

一个“独立密封舱”被定义为一片由一个或多个相连的完好单元组成的区域，该区域在上下左右四个方向上被损坏单元完全包围。

一个重要的前提是：扫描矩阵的外部区域被认为是与飞船主体相连的、广阔的完好区域。因此，任何与矩阵边界直接或间接相连的完好单元区域，都被视作飞船主体结构的一部分，而不是“独立密封舱”。

您的任务是编写一个程序，计算出所有独立密封舱的总面积（即，其中包含的完好单元的总数）。

输入描述

第一行包含两个整数 $M$ 和 $N$ ，分别代表船体截面扫描图的宽度和高度。
接下来的 $N$ 行，每行包含 $M$ 个整数（0 或 1），代表扫描矩阵的每一行。

输出描述

输出一个整数，代表所有独立密封舱的总面积。

解题思路

这个问题的核心是识别并计算那些不与边界相连的完好单元（值为 0）区域。题中有一个关键信息：“扫描矩阵的外部区域被认为是与飞船主体相连的、广阔的完好区域”。这意味着，任何与矩阵边界上的 0 相连通的 0 区域，都不能算作“独立密封舱”。

基于这个特点，我们可以采用一种“逆向思维”或者说“排除法”来解决问题：

识别并标记所有与边界相连的完好区域：
- 我们可以把所有边界上的 0 单元看作是起始点。
- 从这些边界上的 0 开始，进行图的遍历（可以使用广度优先搜索 BFS 或深度优先搜索 DFS）。
- 遍历所有能够从边界 0 到达的 0 单元。
- 将所有这些被访问到的 0 单元做一个特殊标记（例如，将它们的值从 0 修改为 2），表示它们是“外部区域”的一部分，不应被计数。
计算剩余的完好区域：
- 完成第一步后，所有与边界连通的 0 都被标记了。
- 此时，矩阵中仍然保持为 0 的单元，就必然是那些四面八方都被损坏单元（值为 1）或者被我们标记过的“外部”单元所包围的区域。这些正是题目所定义的“独立密封舱”。
- 我们最后再遍历一次整个矩阵，统计所有值仍为 0 的单元的数量，这个总和就是最终的答案。

这个方法巧妙地将一个“寻找封闭区域”的问题，转化为了一个“从边界开始进行 Flood Fill（洪水填充）”的问题，逻辑更清晰，也更容易实现。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M; // N: 高度(行数), M: 宽度(列数)
vector<vector<int>> grid;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

// 检查坐标是否有效
bool is_valid(int r, int c) {
    return r >= 0 && r < N && c >= 0 && c < M;
}

// 从(r, c)开始进行广度优先搜索，标记所有相连的 '0'
void bfs(int r, int c) {
    if (grid[r][c] != 0) {
        return;
    }
    queue<pair<int, int>> q;
    q.push({r, c});
    grid[r][c] = 2; // 标记为已访问的外部区域

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = curr.first + dr[i];
            int nc = curr.second + dc[i];

            if (is_valid(nr, nc) && grid[nr][nc] == 0) {
                grid[nr][nc] = 2;
                q.push({nr, nc});
            }
        }
    }
}

int main() {
    cin >> M >> N; // 先读宽度 M，再读高度 N
    grid.assign(N, vector<int>(M)); // N行 M列
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> grid[i][j];
        }
    }

    // 从所有边界的 '0' 开始进行 BFS
    for (int i = 0; i < N; ++i) { // 遍历左右边界
        bfs(i, 0);
        bfs(i, M - 1);
    }
    for (int j = 0; j < M; ++j) { // 遍历上下边界
        bfs(0, j);
        bfs(N - 1, j);
    }

    // 统计剩余的 '0'，即独立密封舱的面积
    int sealed_area = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (grid[i][j] == 0) {
                sealed_area++;
            }
        }
    }

    cout << sealed_area << endl;

    return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M; // N: 高度(行数), M: 宽度(列数)
    static int[][] grid;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    // 检查坐标是否在网格内
    private static boolean isValid(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }

    // 从(r, c)开始进行广度优先搜索，标记所有相连的 '0'
    private static void bfs(int r, int c) {
        if (grid[r][c] != 0) {
            return;
        }
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c});
        grid[r][c] = 2; // 标记为已访问的外部区域

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            
            for (int i = 0; i < 4; i++) {
                int nr = curr[0] + dr[i];
                int nc = curr[1] + dc[i];

                if (isValid(nr, nc) && grid[nr][nc] == 0) {
                    grid[nr][nc] = 2;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt(); // 先读宽度 M
        N = sc.nextInt(); // 再读高度 N
        grid = new int[N][M]; // N行 M列
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        // 从所有边界的 '0' 开始进行 BFS
        for (int i = 0; i < N; i++) { // 遍历左右边界
            bfs(i, 0);
            bfs(i, M - 1);
        }
        for (int j = 0; j < M; j++) { // 遍历上下边界
            bfs(0, j);
            bfs(N - 1, j);
        }

        // 统计剩余的 '0'，即独立密封舱的面积
        int sealedArea = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 0) {
                    sealedArea++;
                }
            }
        }

        System.out.println(sealedArea);
    }
}

import collections

def solve():
    M, N = map(int, input().split()) # M: 宽度(列数), N: 高度(行数)
    grid = [list(map(int, input().split())) for _ in range(N)]

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    def is_valid(r, c):
        # 检查坐标是否在网格内
        return 0 <= r < N and 0 <= c < M

    def bfs(r, c):
        # 从(r, c)开始进行广度优先搜索，标记所有相连的 '0'
        if grid[r][c] != 0:
            return
        
        q = collections.deque([(r, c)])
        grid[r][c] = 2  # 标记为已访问的外部区域

        while q:
            curr_r, curr_c = q.popleft()
            for i in range(4):
                nr, nc = curr_r + dr[i], curr_c + dc[i]
                if is_valid(nr, nc) and grid[nr][nc] == 0:
                    grid[nr][nc] = 2
                    q.append((nr, nc))

    # 从所有边界的 '0' 开始进行 BFS，标记所有与外界相连的区域
    for i in range(N): # 遍历左右边界
        bfs(i, 0)
        bfs(i, M - 1)
    
    for j in range(M): # 遍历上下边界
        bfs(0, j)
        bfs(N - 1, j)

    # 统计剩余的 '0'，即独立密封舱的面积
    sealed_area = 0
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 0:
                sealed_area += 1
    
    print(sealed_area)

solve()

算法及复杂度

算法: 广度优先搜索 (BFS) / 深度优先搜索 (DFS)
时间复杂度: $O(M \cdot N)$ - 其中 $M$ 和 $N$ 是矩阵的行数和列数。因为每个单元格最多被访问常数次。
空间复杂度: $O(M \cdot N)$ - 在最坏的情况下，BFS的队列或DFS的递归栈可能需要存储所有单元格。