【岛屿个数——BFS / DFS，“外海”】

题目

推荐阅读

AcWing 4959. 岛屿个数（两种解法，通俗解释） - AcWing

1.岛屿个数 - 蓝桥云课 (lanqiao.cn)

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
int dx4[4] = {-1, 0, 1, 0}, dy4[4] = {0, 1, 0, -1};
int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
using PII = pair<int, int>;
const int N = 55;
char g[N][N];
int cnt, m, n;
void bfs_os(int i, int j) // bfs for outer sea, change 0 to 2
{queue<PII> q;g[i][j] = 2;q.push({i, j});while (q.size()){auto u = q.front();q.pop();int x = u.x, y = u.y;for (int i = 0; i < 8; i++){int nx = x + dx8[i];int ny = y + dy8[i];if (nx < 0 || nx > m + 1 || ny < 0 || ny > n + 1 || g[nx][ny])continue;g[nx][ny] = 2; //压入之前改标记，提升速度q.push({nx, ny});}}
}
void bfs_is(int i, int j) // bfs for island, change 1 to 0
{cnt++;queue<PII> q;g[i][j] = 0;q.push({i, j});while (q.size()){auto u = q.front();q.pop();int x = u.x, y = u.y;for (int i = 0; i < 4; i++){int nx = x + dx4[i];int ny = y + dy4[i];if (nx < 1 || nx > m || ny < 1 || ny > n || g[nx][ny] != 1)continue;g[nx][ny] = 0;q.push({nx, ny});}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while (t--){cnt = 0;memset(g, 0, sizeof g);cin >> m >> n;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> g[i][j], g[i][j] -= '0';bfs_os(0, 0);for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){if (g[i][j] == 1 && g[i-1][j] == 2)bfs_is(i, j);}}cout << cnt << '\n';}
}