题解 | 飞船扫描

// 用的广度优先（BFS）

#include <algorithm>
#include <iostream>
#include <queue>
#include <type_traits>
#include <vector>
using namespace std;


struct point {
    int i;
    int j;
};


void MainFunction(vector<vector<int>>& arr, int n, int m) {
    vector<vector<int>> ortherArr;
    for (vector<int> x : arr) ortherArr.push_back(x);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ortherArr[i][j] = -1;
        }
    }

    int s = 0;
    // 统计0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0) s++;
        }
    }

    queue<point> q;
    // 计算联通
    // 第一排
    for (int j = 0; j < m; j++) {
        if (arr[0][j] == 0) {
            point x;
            x.i = 0;
            x.j = j;
            if (ortherArr[x.i][x.j] == 1) continue;
            q.push(x);
            ortherArr[x.i][x.j] = 1;
        }
    }
    // 第一列
    for (int i = 0; i < n; i++) {
        if (arr[i][0] == 0) {
            point x;
            x.i = i;
            x.j = 0;
            if (ortherArr[x.i][x.j] == 1) continue;
            q.push(x);
            ortherArr[x.i][x.j] = 1;
        }
    }
    // 最后一排
    for (int j = 0; j < m; j++) {
        if (arr[n - 1][j] == 0) {
            point x;
            x.i = n - 1;
            x.j = j;
            if (ortherArr[x.i][x.j] == 1) continue;
            q.push(x);
            ortherArr[x.i][x.j] = 1;
        }
    }
    // 最后一列
    for (int i = 0; i < n; i++) {
        if (arr[i][m - 1] == 0) {
            point x;
            x.i = i;
            x.j = m - 1;
            if (ortherArr[x.i][x.j] == 1) continue;
            q.push(x);
            ortherArr[x.i][x.j] = 1;
        }
    }

    while (!q.empty()) {
        point x = q.front();
        q.pop();
        s--;
        if (x.i != 0) {
            if (arr[x.i - 1][x.j] == 0 && ortherArr[x.i - 1][x.j] != 1) {
                point y;
                y.i = x.i - 1;
                y.j = x.j;
                if (ortherArr[y.i][y.j] == 1) continue;
                q.push(y);
                ortherArr[y.i][y.j] = 1;
            }
        }
        if (x.j != 0) {
            if (arr[x.i][x.j - 1] == 0 && ortherArr[x.i][x.j - 1] != 1) {
                point y;
                y.i = x.i;
                y.j = x.j - 1;
                if (ortherArr[y.i][y.j] == 1) continue;
                q.push(y);
                ortherArr[y.i][y.j] = 1;
            }
        }
        if (x.i != n - 1) {
            if (arr[x.i + 1][x.j] == 0 && ortherArr[x.i + 1][x.j] != 1) {
                point y;
                y.i = x.i + 1;
                y.j = x.j;
                if (ortherArr[y.i][y.j] == 1) continue;
                q.push(y);
                ortherArr[y.i][y.j] = 1;
            }
        }
        if (x.j != m - 1) {
            if (arr[x.i][x.j + 1] == 0 && ortherArr[x.i][x.j + 1] != 1) {
                point y;
                y.i = x.i;
                y.j = x.j + 1;
                if (ortherArr[y.i][y.j] == 1) continue;
                q.push(y);
                ortherArr[y.i][y.j] = 1;
            }
        }
    }

    cout << s;
    return ;
}


int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> a(n);
    vector<int> b(m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> b[j];
        }
        a[i] = b;
    }

    MainFunction(a, n, m);

    return 0;
}