蓝桥杯 2023 岛屿个数

题目描述

给定 组测试数据，每组数据是一张 的二值地图，字符 1 表示陆地，字符 0 表示海洋，地图之外视为海水。两个相邻的 1（上、下、左、右四个方向）属于同一个岛屿。若某个岛屿完全被另一个岛屿包围，则称其为子岛屿；统计时只需统计最外层岛屿的数量，子岛屿不计入答案。

输入格式

第一行一个整数 。
接下来每组数据：

  • 第一行两个整数 ；
  • 接下来 行，每行一个长度为 的字符串。

输出格式

对每组数据输出一个整数，表示非子岛屿的数量。

思路

  1. 先从地图边界出发，使用 BFS/DFS 遍历海洋，标记所有与外海相连的海水；
  2. 在外海遍历过程中，如果遇到未访问的陆地，就说明发现了一个新的最外层岛屿，对其进行 BFS/DFS 并标记整座岛；
  3. 如果地图中没有与外海相连的海水，说明整张图都是陆地——此时答案为 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
int grid[N][N];
bool visSea[N][N], visLand[N][N];
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
int dx8[8] = {-1,-1,-1,0,0,1,1,1};
int dy8[8] = {-1,0,1,-1,1,-1,0,1};
int n, m;

inline bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfsLand(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    visLand[sx][sy] = true;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx4[d], ny = y + dy4[d];
            if (inside(nx, ny) && grid[nx][ny] && !visLand[nx][ny]) {
                visLand[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

int bfsSea(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    visSea[sx][sy] = true;
    int islands = 0;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int d = 0; d < 8; ++d) {
            int nx = x + dx8[d], ny = y + dy8[d];
            if (!inside(nx, ny)) continue;
            if (!grid[nx][ny] && !visSea[nx][ny]) {
                visSea[nx][ny] = true;
                q.push({nx, ny});
            } else if (grid[nx][ny] && !visLand[nx][ny]) {
                ++islands;
                bfsLand(nx, ny);
            }
        }
    }
    return islands;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            string s; cin >> s;
            for (int j = 0; j < m; ++j) grid[i][j] = s[j] - '0';
        }
        memset(visSea, 0, sizeof(visSea));
        memset(visLand, 0, sizeof(visLand));

        int ans = 0;
        bool touched = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    if (!grid[i][j] && !visSea[i][j]) {
                        touched = true;
                        ans += bfsSea(i, j);
                    }
                }
            }
        }
        if (!touched) ans = 1;
        cout << ans << '\n';
    }
    return 0;
}