``` 有疑问欢迎讨论😄 #include<bits/stdc++.h> using namespace std; int M,N,cnt; char Map[55][55]; //找外海 int d[8][2]= { {0,-1}, {0,1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1} }; void dfs_sea(int x,int y) { Map[x][y]='2'; for(int i=0;i<8;i++) { int tx=x+d[i][0],ty=y+d[i][1]; if(tx>=0&&tx<=M+1&&ty>=0&&ty<=N+1&&Map[tx][ty]=='0') dfs_sea(tx,ty); } } //找与外海相邻的岛，一定是外岛 void dfs_island(int x,int y) { Map[x][y]='3';//防止主函数里重复搜索 for(int i=0;i<4;i++) { int tx=x+d[i][0],ty=y+d[i][1]; if(tx>=1&&tx<=M&&ty>=1&&ty<=N&&Map[tx][ty]=='1') dfs_island(tx,ty); } } int main() { int T; cin >> T; while(T--) { cin >> M>>N; //把最外圈变成海 for(int i=0;i<=M+1;i++) for(int j=0;j<=N+1;j++) Map[i][j]='0'; //输入地图 for(int i=1;i<=M;i++) for(int j=1;j<=N;j++) cin>>Map[i][j]; dfs_sea(0,0); cnt=0;//答案 for(int i=1;i<=M;i++) { for(int j=1;j<=N;j++) { if(Map[i][j]=='1' && Map[i][j-1]=='2') { dfs_island(i,j); cnt++; } } } cout << cnt<<endl; } return 0; } ```

先用dfs搜索出所有岛屿，并对每个岛屿进行编号。由于岛屿之间互相隔离，则如果岛屿的一个格子在一个环内，那么整个岛屿也都在环内。遍历所有的岛屿，选中当前岛屿的第一个格子，搜索周围海洋（当被一个环岛包围时，八个方向都不能穿过，反之则没有被环岛包围），若能搜索到地图的边界外，则此岛屿不在任何一个环内，则岛屿数+1，否则，该岛屿在某一个环岛内，则不需要加入该岛屿。 ``` #include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; int n, m; //存储每一个岛屿的第一个格子的基本信息 class Data{ public: char number;//编号 int x, y;//坐标 Data(){} Data(char nubmer, int x, int y){ this->number = number; this->x = x; this->y = y; } }; //方向数组 //上 下 左 右 左上 左下 右上 右下 int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1}; int dy[] = {0, 0, -1, 1, -1, -1, 1, 1}; //dfs对岛屿进行编号 void dfs(vector<string>& graph, int i, int j, char number){ graph[i][j] = number; //给岛屿编号，只需要 上下左右四个方向 for(int k = 0;k < 4;k++){ int x = i + dx[k]; int y = j + dy[k]; if(x>=0 && x<n && y>=0 && y<m && graph[x][y] == '1'){ dfs(graph, x, y, number); } } } //bfs判断该岛屿是否能到达外海（能到达则该岛屿没有被包围住） bool bfs(vector<string> graph, int i, int j){ queue<pair<int, int>> que; que.push({i, j}); while(!que.empty()){ //抵达外海需要8个方向 for(int k = 0;k < 8;k++){ int x = que.front().first + dx[k]; int y = que.front().second + dy[k]; //到外海了 => 越界 if(x<0 || x>=n || y<0 || y>=m) return true; if(graph[x][y] == '0'){ graph[x][y] = '-1'; que.push({x, y}); } } que.pop();//出队 } return false;//没有到外海 } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; while(T--){ cin >> n >> m; int ans = 0; vector<string> graph(n, "");//初始化 vector<Data> land; for(int i = 0;i < n;i++){ cin >> graph[i];//输入图 } //遍历图，给图编号 char number = '2'; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(graph[i][j] == '1'){ //传入第一个岛的信息 land.push_back(Data(number, i, j)); dfs(graph, i, j, number); number++; } } } //遍历每个岛屿的第一个位置，如果该位置能到达最外海的位置，则该岛独立 for(auto it : land){ if(bfs(graph, it.x, it. y)) ans++; } cout << ans << endl; //打印 被标号后的岛屿 // for(int i = 0;i < n;i++){ // for(int j = 0;j < m;j++){ // cout << graph[i][j] << " "; // } // cout << endl; // } } return 0; } ```

``` #include <iostream> #include <queue> #include <cstring> using namespace std; const int N = 55; #define pii pair<int, int> #define ft first #define sd second int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1};//八个方向 int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1}; char g[N][N];//地图 int t[N][N], st[N][N];//标记已访问过的点 int n, m, res;//n，m表示行列，res用来记录满足条件的连通块数目 //用于搜索连通块 void bfs(int i, int j) { queue<pii> q;//用于储存待访问的点 q.push({i, j}); while (!q.empty()) { int x = q.front().ft, y = q.front().sd; q.pop(); if (t[x][y]) continue; t[x][y] = true; for (int i = 0; i < 8; i++) { int xx = x + dx[i], yy = y + dy[i]; if (t[xx][yy] || xx < 1 || xx > n || yy < 1 || yy > m || g[xx][yy] == '0') continue; q.push({xx, yy}); } } } //用于检查连通块是否与边界连接 bool check(int i, int j) { queue<pii> q; q.push({i, j}); while (!q.empty()) { int x = q.front().ft, y = q.front().sd; q.pop(); if (st[x][y]) continue; st[x][y] = true; if (x == 1 || x == n || y == 1 || y == m) return true; for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (st[xx][yy] || g[xx][yy] == '1') continue; q.push({xx, yy}); } } return false; } void solve() { memset(t, 0, sizeof t); res = 0; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> g[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!t[i][j] && g[i][j] == '1') { bfs(i, j); memset(st, 0, sizeof st);//初始化边界标记数组 if (check(i, j)) res++;//检查当前连通块是否与边界相连接，并更新结果 } } } cout << res << endl; } int main() { int T; cin >> T; while(T--) solve(); return 0; } ```

``` #include <bits/stdc++.h> using namespace std; const int N = 55; char g[N][N]; bool ist[N][N]; int t, n, m, ans; const int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1}; bool check(int i, int j) { bool ist_[N][N]; memset(ist_, false, sizeof ist_); queue<pair<int, int>> q; q.push({i, j}); while (q.size()) { auto cur = q.front(); q.pop(); for (int i = 0; i < 8; i ++) { auto x = cur.first + dx[i]; auto y = cur.second + dy[i]; if (x < 0 || y < 0 || x >= n || y >= m) return true; if (g[x][y] == '0' && !ist_[x][y]) { ist_[x][y] = true; q.push({x, y}); } } } return false; } void bfs(int i, int j) { queue<pair<int, int>> q; q.push({i, j}); ist[i][j] = true; while (q.size()) { auto cur = q.front(); q.pop(); for (int i = 0; i < 4; i ++) { auto x = cur.first + dx[i]; auto y = cur.second + dy[i]; if (x >= 0 && x < n && y < m && y >= 0 && g[x][y] == '1' && !ist[x][y]) { ist[x][y] = true; q.push({x, y}); } } } } void solve() { memset(g, '0', sizeof g); cin >> n >> m; for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { cin >> g[i][j]; } } for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { if (!ist[i][j] && g[i][j] == '1') { bfs(i, j); ans += check(i, j) ? 1 : 0; } } } cout << ans << '\n'; } int main(void) { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> t; for (int i = 0; i < t; i ++) { solve(); ans = 0; memset(ist, false, sizeof ist); memset(g, '0', sizeof g); } } ```

1. 先从(0,0)开始走八步将外围海水染成2，那么目标范围地图内的0一定为岛内海水； 2. 将岛内海水（地图中的0全部变成陆地）即填海造陆； 3. 统计岛的个数； include using namespace std; struct dps{ int x; int y; }; char mp[55][55]; int m,n; int dx[8]={-1,0,1,0,-1,1,1,-1}; int dy[8]={0,1,0,-1,1,1,-1,-1}; int ans[15]; void bfs1(dps a) { queue q; q.push(a); mp[a.x][a.y]='2'; while(!q.empty()) { dps t=q.front(); q.pop(); for(int i=0;i =0&&tx =0&&ty q; q.push(a); mp[a.x][a.y]='2'; while(!q.empty()) { dps t=q.front(); q.pop(); for(int i=0;i =1&&tx =1&&ty >t; for(int i=0;i<t;i++) { for(int j=0;j<55;j++)//地图初始为'0' for(int k=0;k<55;k++) mp[j][k]='0'; ``` cin>>m>>n; for(int j=1;j<=m;j++)//输入mp for(int k=1;k<=n;k++) cin>>mp[j][k]; dps te; te.x=0,te.y=0; bfs1(te);//将外围海水标成2 for(int j=1;j<=m;j++)//将岛内海水变成土 for(int k=1;k<=n;k++) { if(mp[j][k]=='0') mp[j][k]='1'; } for(int j=1;j<=m;j++)//统计岛的个数 for(int k=1;k<=n;k++) { if(mp[j][k]=='1') { dps t={j,k}; bfs2(t); ans[i]++; } } } for(int i=0;i<t;i++) cout<<ans[i]<<endl; return 0; ``` }

没找到错误原因 ``` #include <bits/stdc++.h> #define endl '\n' #define ll long long using namespace std; const int N = 50+5; const int M = 50+5; bool waihai = false; int m,n; int g[M][N]; bool landvit[M][N]; bool seavit[M][N]; int res; //方向 int ldx[4]={0,0,1,-1}; int ldy[4]={1,-1,0,0}; int sdx[8]={-1,-1,-1,0,0,1,1,1}; int sdy[8]={-1,0,1,1,-1,1,-1,0}; //跟海洋bfs很像 void landbfs(int x, int y){ landvit[x][y] = true; queue<pair<int,int>> q; q.push(make_pair(x,y)); while(!q.empty()){ pair<int, int> cur = q.front(); q.pop(); int xx = cur.first; int yy = cur.second; for(int i =0;i<4;i++){ int nx = xx + ldx[i]; int ny = yy + ldy[i]; if(nx<1||nx>m||ny<1||ny>n)continue; //同一个岛上没访问过的陆地 if(g[nx][ny]==1&&landvit[nx][ny]==false){ landvit[nx][ny] = true; q.push(make_pair(nx,ny)); } } } } //遍历海洋，遇到陆地调用陆地bfs 遇到海洋打标记 void seabfs(int x, int y){ //初始化起始点 seavit[x][y] = true; queue<pair<int,int>> q; q.push(make_pair(x,y)); while(!q.empty()){ pair<int, int> cur = q.front(); q.pop(); int xx = cur.first; int yy = cur.second; //将这个点的邻域加入队列 for(int i = 0; i<8;i++){ int nx = xx + sdx[i]; int ny = yy + sdy[i]; if(nx<1||nx>m||ny<1||ny>n)continue; if(g[nx][ny]==1&&landvit[nx][ny]==false){ //是没访问过的陆地,找到了一个新岛 res++; //遍历岛的所有陆地，打标记免得重复计算 landbfs(nx,ny); } if(g[nx][ny]==0&&seavit[nx][ny]==false){ //是没访问过的海洋,入队 seavit[nx][ny] = true; q.push(make_pair(nx,ny)); } } } } void solve(){ //多轮数据 清空前面的 memset(landvit,false,sizeof(landvit)); memset(seavit,false,sizeof(seavit)); res = 0; //初始化图 cin >>m >> n; //输入的数字之间无空格 得先string读进来切分 for(int i =1;i<=m;i++){ string s; cin >> s; for(int j =1;j<=n;j++){ g[i][j] = s[j] - '0'; } } //最外圈找外海点作为seabfs起点 for(int i=1;i<=m;i++){ for(int j =1;j<=n;j++){ if(i==1||i==m||j==1||j==n){ //外圈点 //没访问过的海 if(seavit[i][j]==false&&g[i][j]==0){ waihai = true; seabfs(i,j); } } } } if(waihai == false){ res = 1; } cout << res << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; // t = 1; while(t--){ solve(); } return 0; } ```

``` from collections import deque dirsea =[(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(-1,1),(1,-1)] dirland = [(1,0),(-1,0),(0,1),(0,-1)] def bfsland(x,y): qland = deque() qland.appendleft((x,y)) vis_island[x][y] =1 while qland: x,y = qland.popleft() for l in range(4): nx = x+dirland[l][0] ny = y+dirland[l][1] if nx>=m or nx<0 or ny>=n or ny<0: continue if maze[nx][ny] =='1' and vis_island[nx][ny]==0: vis_island[nx][ny] =1 qland.appendleft((nx,ny)) def bfssea(x,y): global ans qsea = deque() qsea.appendleft((x,y)) vis_sea[x][y] = 1 while qsea: x,y = qsea.popleft() for k in range(8): nx =x+dirsea[k][0] ny = y + dirsea[k][1] if nx>=m or nx<0 or ny>=n or ny<0: continue if maze[nx][ny] == '0' and vis_sea[nx][ny]==0: qsea.appendleft((nx,ny)) vis_sea[nx][ny]=1 if maze[nx][ny] =='1' and vis_island[nx][ny]==0: ans +=1 bfsland(nx,ny) for i in range(int(input())): m,n = map(int,input().split()) maze = [] ans = 0 for i in range(m): maze.append(input()) vis_island = [[0]*n for i in range(m)] vis_sea = [[0]*n for i in range(m)] flag =0 for i in range(m): for j in range(n): if (not i or i == m-1 or j ==n-1 or not j): if maze[i][j] == '0' and vis_sea[i][j]==0: flag=1 bfssea(i,j) if not flag: ans =1 print(ans) ```

🎉️ ```cpp #include <cstdio> #include <vector> #include <tuple> #include <queue> #include <utility> #include <functional> using namespace std; const int x_fx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; const int y_fx[8] = {0, 1, 0, -1, 1, 1, -1, -1}; void hx() { int n, m; scanf("%d %d", &n, &m); vector<vector<char>> tizi(n, vector<char>(m)); for (int i = 0; i < n; ++i) { char tmp[128]; scanf("%s", tmp); for (int j = 0; j < m; ++j) { tizi[i][j] = tmp[j]; } } int res = 0; vector<vector<char>> vis(n, vector<char>(m)); queue<pair<int, int>> pq; function<void(int, int)> dfs = [&](int i, int j) { if (i < 0 || j < 0 || i >= n || j >= m || vis[i][j] || tizi[i][j] == '0') return; vis[i][j] = 1; pq.push(make_pair(i, j)); for (int k = 0; k < 4; ++k) { dfs(i + y_fx[k], j + x_fx[k]); } }; function<void()> bfs = [&]() { vector<vector<char>> kairyu(n, vector<char>(m)); while (pq.size()) { int i, j; tie(i, j) = pq.front(); kairyu[i][j] = 1; pq.pop(); // 向八方向跑 for (int k = 0; k < 8; ++k) { int y = i + y_fx[k]; int x = j + x_fx[k]; if (x < 0 || y < 0 || y >= n || x >= m) { // 逃出去海了, 直接返回! ++res; pq = queue<pair<int, int>>(); // 清空 return; } if (!kairyu[y][x] && tizi[y][x] == '0') { kairyu[y][x] = 1; pq.push(make_pair(y, x)); } } } }; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (tizi[i][j] == '1') { dfs(i, j); // dfs 把整个岛放进去 bfs(); // bfs 岛上的每一个点尝试跑出地图外 (如果可以跑出去, 说明没有被岛包围) } } } printf("%d\n", res); } int main() { int t; scanf("%d", &t); while (t--) hx(); return 0; } ```