题在这里：https://www.lanqiao.cn/problems/3513/learning/?page=1&first_category_id=1&second_category_id=3&tag_relation=intersection&name=%E5%B2%9B%E5%B1%BF

看了很多bfs和dfs的题，让我印象最深刻的就是这个求各种岛屿数量的题，本题也是一样，只不过是要求外岛也就是非子岛的数量，刚拿到题的时候我也是刚复习完深搜和广搜，我寻思我对这个广搜的过程最不熟悉，这个题我按照思路使用广搜完成吧，本题的思路和前面几个简单的岛屿计算类似，我们先找到所有的外海点，从每一个外海点入手，去遍历也就是广搜储存相邻的外海，然后在搜索的过程中，如果遍历到陆地就再进入广搜搜索相对于的外岛，注第一次进入搜索陆地的dfs的时候就将计数器++，避免重复记录，同时还有两个关键点一是本题的陆地遍历是4个方向，但是海水是8个方向，二是符合广搜的元素进入队列就将其置为true而不是出队列才置为true要不然会出现相同元素重复入队列的情况。导致超时。

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 52;
#define int long long

int res, m, n;
int dir_road[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
int dir_sea[8][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}, {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};

void bfs_road(const vector<vector<int>> &grid, vector<vector<bool>> &visited_road, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    visited_road[x][y] = true;
    // res++;  // 进入 BFS 就计数

    while (!que.empty()) {
        auto [curx, cury] = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dir_road[i][0];
            int nexty = cury + dir_road[i][1];

            if (nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) continue;
            if (grid[nextx][nexty] == 1 && !visited_road[nextx][nexty]) {
                que.push({nextx, nexty});
                visited_road[nextx][nexty] = true;
            }
        }
    }
}

void bfs_sea(const vector<vector<int>> &grid, vector<vector<bool>> &visited_sea, vector<vector<bool>> &visited_road, int x, int y) {
    queue<pair<int, int>> que;
    que.push({x, y});
    visited_sea[x][y] = true;

    while (!que.empty()) {
        auto [curx, cury] = que.front();
        que.pop();
        for (int i = 0; i < 8; i++) {
            int nextx = curx + dir_sea[i][0];
            int nexty = cury + dir_sea[i][1];

            if (nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) continue;
            if (grid[nextx][nexty] == 0 && !visited_sea[nextx][nexty]) {
                que.push({nextx, nexty});
                visited_sea[nextx][nexty] = true;
            }
            if (grid[nextx][nexty] == 1 && !visited_road[nextx][nexty]) {
                res++;
                bfs_road(grid, visited_road, nextx, nexty);
            }
        }
    }
}

void solve() {
    cin >> m >> n;
    res = 0;

    vector<vector<int>> grid(m, vector<int>(n, 0));
    vector<vector<bool>> visited_sea(m, vector<bool>(n, false));
    vector<vector<bool>> visited_road(m, vector<bool>(n, false));

    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            grid[i][j] = s[j] - '0';
        }
    }

    // 先找到所有外海，进行 BFS 标记
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                if (grid[i][j] == 0 && !visited_sea[i][j]) {
                    bfs_sea(grid, visited_sea, visited_road, i, j);
                }
            }
        }
    }

    cout << res << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}