本题题解，我在洛谷上面能AC但是群主这个oj不行，大家看看就可以了。 ``` #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,cnt,sum,ans,t,dx[]={0,1,0,-1},dy[]={1,0,-1,0}; char mp[1010][1010]; void dfs(int x,int y) { if(!t)//一块大陆与海洋相连接 { cnt=0; for(int i=0;i<4;i++) if(mp[x+dx[i]][y+dy[i]]!='.')cnt++; if(cnt==4)//周围全是岛屿没有海洋 ans++,t=1;//这个岛屿代表t } mp[x][y]='*';//标记 for(int i=0;i<4;i++) { int xx=x+dx[i],yy=y+dy[i]; if(xx<0||xx>=n||yy<0||yy>=n||mp[xx][yy]!='#')continue; dfs(xx,yy); } } int main() { cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>mp[i][j]; for(int i=1;i<n-1;i++) for(int j=1;j<n-1;j++) if(mp[i][j]=='#') { sum++; t=0; dfs(i,j); } cout<<sum-ans; } ```

BFS 1. 读取包含陆地（'#'）和大海（'.'）的地图数据。 2. 对地图进行遍历，对每个未被搜索过的陆地进行广度优先搜索（BFS），统计搜索到的陆地单元格数（total）和与大海相连的边界单元格数（bound）。 3. 判断一个岛屿是否被完全淹没的标准是：搜索到的陆地单元格数等于与大海相连的边界单元格数。若满足此条件，计数器cnt加一。 ``` .cpp #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010; int n; char g[N][N]; // 二维数组 g 存储地图，'#' 表示陆地，'.' 表示大海 bool st[N][N]; // 记录每个格子是否被搜索过，初始均为 false PII q[N * N]; // 定义一个队列用于广度优先搜索 int dx[4] = {-1, 0, 1, 0}; // 四个方向的水平偏移量 int dy[4] = {0, 1, 0, -1}; // 四个方向的垂直偏移量 // 广度优先搜索函数，参数：搜索起点坐标（sx, sy），累计搜索到的陆地单元格数（total），与大海相连的边界单元格数（bound） void bfs(int sx, int sy, int &total, int &bound) { int hh = 0, tt = 0; // hh：队首指针，tt：队尾指针 q[0] = {sx, sy}; // 将起点加入队列 st[sx][sy] = true; // 标记起点已被搜索过 while (hh <= tt) { // 当队列不为空时 PII t = q[hh++]; // 弹出队首元素 total++; // 增加已搜索到的陆地单元格数 bool is_bound = false; // 标记当前格子是否与大海相连 // 遍历当前格子的四个方向 for (int i = 0; i < 4; i++) { int x = t.x + dx[i], y = t.y + dy[i]; // 计算相邻格子坐标 // 检查是否越界 if (x < 0 || x >= n || y < 0 || y >= n) continue; // 如果相邻格子已被搜索过，跳过本次循环 if (st[x][y]) continue; // 检查相邻格子类型 if (g[x][y] == '.') { is_bound = true; // 标记当前格子与大海相连 continue; } // 如果相邻格子是未搜索过的陆地，将其加入队列并标记为已搜索 q[++tt] = {x, y}; st[x][y] = true; } // 如果当前格子与大海相连，增加边界单元格数 if (is_bound) bound++; } } int main() { scanf("%d", &n); // 输入地图大小 // 读取地图数据 for (int i = 0; i < n; i++) scanf("%s", g[i]); int cnt = 0; // 初始化被淹没岛屿个数 // 遍历地图，对每个未被搜索过的陆地进行广度优先搜索 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (!st[i][j] && g[i][j] == '#') { // 检查是否为未搜索过的陆地 int total = 0, bound = 0; // 初始化单元值和边界数量 bfs(i, j, total, bound); // 对当前陆地进行广度优先搜索 // 如果搜索到的陆地单元格数等于与大海相连的边界单元格数，说明该岛屿被完全淹没，计数器加一 if (total == bound) cnt++; } } printf("%d\n", cnt); // 输出被淹没岛屿个数 return 0; } ```

注意！注意！注意！ 要加边界判定， 最外面一层有岛屿！！！ ```cpp #include <iostream> using namespace std; const int N = 1010; int n; char d[N][N]; bool st[N][N]; int res; bool flag; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, -1, 0, 1}; void dfs(int x, int y) { st[x][y] = true; bool ret = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 1 && nx <= n && nx >= 1 && ny <= n) // 要判断边界 { if (d[nx][ny] == '.') ret = false;// 如果周围有水的话就表示被淹了 } } if (ret) flag = true; if (d[x - 1][y] == '#' && d[x + 1][y] == '#' && d[x][y - 1] == '#' && d[x][y + 1] == '#') flag = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 1 && nx <= n && nx >= 1 && ny <= n) { if (!st[nx][ny] && d[nx][ny] == '#') dfs(nx, ny); } } } int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> d[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (!st[i][j] && d[i][j] == '#') { flag = false; dfs(i, j); if (!flag) res += 1; } } cout << res << endl; system("pause"); return 0; } ```

这里给大家提供两种解法，dfs和bfs dfs解法 ``` #include <bits/stdc++.h> using namespace std; const int N = 1010; char mp[N][N]; int n; int flag = 0; int vis[N][N]; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; void dfs(int x,int y){ vis[x][y] = true; for (int i = 0; i < 4; ++i){ int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > n) continue; if (mp[nx][ny] == '.') continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; if (mp[nx - 1][ny] == '#' && mp[nx + 1][ny] == '#' && mp[nx][ny - 1] == '#' && mp[nx][ny + 1] == '#'){ flag = 1; } dfs(nx,ny); } return; } int main(){ int sum = 0; int cnt = 0; scanf("%d",&n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { cin >> mp[i][j]; } } for (int i = 0; i <= n + 1; ++i){ for (int j = 0; j <= n + 1; ++j){ if (!mp[i][j]) mp[i][j] = '#'; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (mp[i][j] == '#' && !vis[i][j]){ dfs(i,j); sum++; if (flag == 1){ cnt++; flag = 0; } } } } printf("%d\n",sum - cnt); return 0; } ``` bfs解法 ``` #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; queue<PII> q; const int N = 1010; int n; int flag = 0; char mp[N][N]; int vis[N][N]; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; void bfs(int x,int y){ vis[x][y] = 1; q.push({x,y}); while(!q.empty()){ PII t = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int nx = t.first + dx[i]; int ny = t.second + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > n) continue; if (mp[nx][ny] == '.') continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; if (mp[nx - 1][ny] == '#' && mp[nx + 1][ny] == '#' && mp[nx][ny - 1] == '#' && mp[nx][ny + 1] == '#'){ flag = 1; } q.push({nx,ny}); } } } int main(){ int sum = 0; int cnt = 0; scanf("%d",&n); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j){ cin >> mp[i][j]; } } for (int i = 0; i <= n + 1; ++i) { for (int j = 0; j <= n + 1; ++j) { if (!mp[i][j]) mp[i][j] = '#'; } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (mp[i][j] == '#' && !vis[i][j]){ bfs(i,j); sum ++; if (flag == 1){ cnt++; flag = 0; } } } } printf("%d\n",sum - cnt); return 0; } ``` 所有数据均可通过

``` n = int(input()) # 输入地图的大小 a = [input() for _ in range(n)] # 存储地图的数组 # print(*a, sep='\n') # 打印地图 flag = 0 # 用于标记岛屿是否被完全淹没 vis = [[0] * n for _ in range(n)] # 标记是否搜过的二维数组 dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 四个方向（上、右、下、左）的偏移量 def dfs(x, y): global flag vis[x][y] = 1 # 标记当前位置已经被搜索过 if (x - 1 < 0 or a[x - 1][y] == '#') and (y + 1 > n - 1 or a[x][y + 1] == '#') and (x + 1 > n - 1 or a[x + 1][y] == '#') and (y - 1 < 0 or a[x][y - 1] == '#'): flag = 1 # 若周围都是陆地不会被淹没 for dx, dy in dirs: # 搜索当前位置的四个相邻位置 nx, ny = x + dx, y + dy if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1: # 地图边界 continue if a[nx][ny] == '#' and vis[nx][ny] == 0: # 如果相邻位置是未搜索过的陆地 dfs(nx, ny) # 继续搜索其相邻位置 cnt = 0 # DFS所有像素点 for i in range(n): for j in range(n): # 如果当前位置是陆地且未被搜索过 if a[i][j] == '#' and vis[i][j] == 0: flag = 0 dfs(i, j) if flag == 0: cnt += 1 print(cnt) ```

测试数据与题目不符，有界限的问题 ``` #include <bits/stdc++.h> using namespace std; #define int long long int n; vector<vector<char>>arr1; vector<vector<char>>arr2; vector<pair<int,int>>dao; map<pair<int,int>,bool> vis; set<int> num; set<int> num2; map<pair<int,int>,int> f; vector<vector<int>>dir = {{-1,0},{1,0},{0,-1},{0,1}}; void dfs(pair<int,int> node ,int flag){ if(vis[node]){ return ; } f[node] = flag; vis[node] = true; num.insert(flag); for(int i=0;i<4;i++){ int x =node.first + dir[i][0]; int y = node.second + dir[i][1]; if(x<0||y<0||x>=n||y>=n) continue; if(arr1[x][y]=='.'){ arr2[node.first][node.second] = '.'; } if(arr1[x][y]=='#'&&!vis[{x,y}]){ dfs(pair<int,int>({x,y}),flag); } } } signed main(){ // int n; cin>>n; arr1 = vector<vector<char>>(n,vector<char>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>arr1[i][j]; if(arr1[i][j]=='#'){ dao.push_back({i,j}); } } } arr2 = arr1; int flag = 1; for(auto& e:dao){ dfs(e,flag); flag++; } for(auto& e:dao){ if(arr2[e.first][e.second] == '#'){ num2.insert(f[e]); } } cout<<num.size() - num2.size(); return 0; } ```

``` #include<bits/stdc++.h> using namespace std; char a[1010][1010]; int vis[1010][1010]={0}, d[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; int flag; void dfs(int x, int y) { vis[x][y] = 1; if (a[x + 1][y] != '.' && a[x - 1][y] != '.' && a[x][y + 1] != '.' && a[x][y - 1] != '.') flag = 1; for (int i = 0; i < 4; i++) { //int nx = x + d[i][0], ny = y + d[i][1]; if (a[x + d[i][0]][y + d[i][1]] == '#' && vis[x + d[i][0]][y + d[i][1]] == 0) dfs(x + d[i][0], y + d[i][1]); } } int main() { int N; cin >> N; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { cin >> a[i][j]; } int ans=0; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { if (a[i][j] == '#' && vis[i][j] == 0) { flag = 0; dfs(i, j); if (flag == 0) ans++; } } cout << ans<<endl; return 0; } ```

``` #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e3 + 10, M = N * N; char g[N][N]; int n, ans, vis[N][N]; int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; bool flag = true; // 假设被淹没 void has_submerge(int sx, int sy) { vis[sx][sy] = 1; bool has_water = false; // 假设周围没有水 for(int i = 0; i < 4; i++) // 遍历四个方向 { int x = sx + dx[i], y = sy + dy[i]; if(x < 0 || y < 0 || x >= n || y >= n) continue; if(vis[x][y] ) continue; if(g[x][y] == '.'){ has_water = true; continue;} vis[sx][sy] = 1; has_submerge(x, y); } if(!has_water) flag = false; // 四个方向循环完再去更新flag } int main() { cin >> n; for(int i = 0; i < n; i++) cin >> g[i]; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(g[i][j] == '#' && !vis[i][j]) { flag = true; has_submerge(i, j); if(flag) ans ++; } cout << ans << endl; return 0; } ```

```cpp // https://dashoj.com/d/lqbproblem/p/54 #include <bits/stdc++.h> #define N 1010 using namespace std; typedef long long ll; ll n; char g[N][N]; // 存图 //vector<vector<char>> g(N, vector<char>(N)); // 存图 bool b[N][N]; // 是否被访问过 //vector<vector<bool>> b(N, vector<bool>(N, true)); // 是否被访问过 bool t = false; ll ans = 0; int dx[4] = {-1, 0, 1, 0}; // 移动 int dy[4] = {0, 1, 0, -1}; void dfs(int x, int y) { if (g[x][y] == '.' || !b[x][y]) { // 是海洋或者已被访问过 return; } b[x][y] = false; // 设为访问过 if (g[x - 1][y] != '.' && g[x][y + 1] != '.' && g[x + 1][y] != '.' && g[x][y - 1] != '.') { // 如果四个方向不是海洋 t = true; // 没有沉没 } for (int i = 0; i < 4; i++) { // 访问四个方向 int vx = x + dx[i], vy = y + dy[i]; if (vx >= n || vy >= n || vx < 0 || vy < 0) { // 检测出界 continue; } if (b[vx][vy]) { dfs(vx, vy); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; fill(&b[0][0], &b[0][0] + N * N, true); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> g[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j] == '#' && b[i][j]) { // 是陆地且未被访问过 t = false; dfs(i, j); if (!t) { ans++; } } } } cout << ans << endl; return 0; } ```

``` #include<algorithm> #include<iostream> using namespace std; char position[1010][1010]; int flagt=0; int flag[1010][1010]; int flag2[1010][1010]; int n; void dfs(int y,int x){ if(position[y][x]=='.'||flag[y][x]||(y<1||y>n||x<1||x>n)) return ; if(position[y+1][x]!='.'&&position[y-1][x]!='.'&&position[y][x-1]!='.'&&position[y][x+1]!='.') flagt=1; flag[y][x]=1; dfs(y+1,x); //up dfs(y,x-1); //left dfs(y-1,x); //down dfs(y,x+1); //right return ; } int main(){ int count=0; int count2=0; cin>>n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin>>position[i][j]; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ if (position[i][j]=='.'||flag[i][j]==1) continue; else{ count++; flagt=0; dfs(i,j); if(flagt) count2++; } } cout<<count-count2; return 0; } ```