84 lines
2.1 KiB
C++
84 lines
2.1 KiB
C++
// lanqiao3513 岛屿个数
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e2 + 10;
|
|
int t, n, m, ans, flag;
|
|
char g[N][N];
|
|
bool vis[N][N];
|
|
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; // 搜岛屿连通块的方向数组
|
|
int dx1[] = {0, 0, 1, -1, 1, 1, -1, -1}, dy1[] = {1, -1, 0, 0, 1, -1, 1, -1}; // 搜外海的方向数组
|
|
|
|
// 搜索独立岛屿-连通块
|
|
void dfs_land(int x, int y){
|
|
for(int i = 0; i < 4; i++){
|
|
int bx = x + dx[i], by = y + dy[i];
|
|
if(bx < 1 || bx > n || by < 1 || by > m) continue;
|
|
if(vis[bx][by] || g[bx][by] == '0') continue;
|
|
vis[bx][by] = 1;
|
|
dfs_land(bx, by);
|
|
}
|
|
}
|
|
|
|
// 搜索外海-独立岛屿(非内环岛)
|
|
void dfs_sea(int x, int y){
|
|
if(x == 0 || x == n + 1 || y == 0 || y == m + 1){
|
|
flag = true;
|
|
return;
|
|
}
|
|
for(int i = 0; i < 8; i++){
|
|
int bx = x + dx1[i], by = y + dy1[i];
|
|
if(bx < 0 || bx > n + 1 || by < 0 || by > m + 1) continue;
|
|
if(vis[bx][by] || g[bx][by] == '1') continue;
|
|
vis[bx][by] = 1;
|
|
dfs_sea(bx, by);
|
|
}
|
|
}
|
|
|
|
int main(){
|
|
cin >> t;
|
|
while(t--){
|
|
cin >> n >> m;
|
|
for(int i = 0; i <= n + 1; i++){
|
|
for(int j = 0; j <= m + 1; j++){
|
|
if(i == 0 || i == n + 1 || j == 0 || j == m + 1) g[i][j] = '0'; // 添加外海
|
|
else cin >> g[i][j];
|
|
}
|
|
}
|
|
ans = 0;
|
|
// 查找岛屿连通块
|
|
memset(vis, 0, sizeof vis);
|
|
vector<pair<int, int>> vec;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= m; j++){
|
|
if(g[i][j] == '1' && !vis[i][j]){
|
|
vis[i][j] = 1;
|
|
vec.push_back({i, j}); // 记录连通块的点
|
|
dfs_land(i, j);
|
|
}
|
|
}
|
|
}
|
|
for(auto it:vec){
|
|
memset(vis, 0, sizeof vis);
|
|
flag = false;
|
|
dfs_sea(it.first, it.second);
|
|
if(flag) ans++;
|
|
}
|
|
cout << ans << endl;
|
|
}
|
|
return 0;
|
|
}
|
|
/* samples -> 1 3
|
|
2
|
|
5 5
|
|
01111
|
|
11001
|
|
10101
|
|
10001
|
|
11111
|
|
5 6
|
|
111111
|
|
100001
|
|
010101
|
|
100001
|
|
111111
|
|
*/ |