//因为不能加上子岛屿的数目,所以只需要把环形的岛屿内部全部填充成‘1’,那么便可以放心用bfs进行搜索,无需再考虑子岛屿的问题
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 60;
char a[N][N];
bool state[N][N];
int q,p;
struct des {
int x, y;
};
void bfs1(des start) //bfs1用于对环状岛屿的填充
{
int cnt = 0;
queue<des> b, c; //b队列用于搜索‘0’,c队列用于记录遍历的‘0’的坐标
b.push(start), c.push(start);
int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1}; //具体可借鉴 样例2 来理解
while (b.size())
{
des m = b.front();
b.pop();
for (int i = 0; i < 8; i++)
{
int X = m.x + dx[i];
int Y = m.y + dy[i];
if (X < 0 || Y < 0 || Y >= p || X >= q)continue;
if (state[X][Y] == 1)continue;
if (a[X][Y] == '1')continue;
b.push({ X,Y }), c.push({ X,Y });
state[X][Y] = 1;
if (X == 0 || Y == 0 || X == q - 1 || Y == p - 1)cnt++; //是否有‘0’能够接触到边缘
}
}
if (cnt == 0)
{
int s = c.size();
for (int i = 0; i < s; i++)
{
a[c.front().x][c.front().y] = '1';
c.pop();
}
}//cnt==0表示没有一个‘0’能接触边缘,即这是一个环状岛屿,用‘1’填充整个环形岛屿内部
}
int bfs2(des start) //bfs2用于搜索岛屿的个数
{
queue<des> d;
d.push(start);
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
while (d.size())
{
des m = d.front();
d.pop();
for (int i = 0; i < 4; i++)
{
int X = m.x + dx[i];
int Y = m.y + dy[i];
if (X < 0 || Y < 0 || Y >= p || X >= q)continue;
if (state[X][Y] == 1)continue;
if (a[X][Y] == '0')continue;
d.push({ X,Y });
state[X][Y] = 1;
}
}
return 1;
}
int main()
{
int k;
cin >> k;
while (k--)
{
int sum=0;
memset(state, 0, sizeof state);
cin >> q >> p;
for (int i = 0; i < q; i++)scanf("%s", a[i]);
for (int i = 1; i < q; i++)
for (int j = 1; j < p; j++)
if (a[i][j] == '0' && state[i][j] == 0)bfs1({ i,j });
memset(state, 0, sizeof state);
for (int i = 0; i < q; i++)
for (int j = 0; j < p; j++)
if (a[i][j] == '1' && state[i][j] == 0)sum += bfs2({ i,j });
cout << sum << endl;
}
return 0;
}
牛