岛屿的数量(考试的时候题目都看不懂啊啊啊)(现在看了好几遍懂了)
作者:
炽热小老弟
,
2023-04-16 10:28:21
,
所有人可见
,
阅读 203
只能过一个点 内部有环的没判断 待更改
#include <iostream>
#include <cstring>
#include <algorithm>
#include<cmath>
using namespace std;
const int N = 55;
typedef pair<int,int>PII;
char g[55][55];
PII q[N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int bfs(int n,int m)
{
int res=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(!st[i][j]&&g[i][j]=='1')
{
res++;
int hh=0,tt=-1;
q[++tt]={i,j};
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int x=dx[i]+t.first,y=dy[i]+t.second;
if(x>=0&&y>=0&&x<n&&y<m&&!st[x][y]&&g[x][y]=='1')
{
st[x][y]=1;
q[++tt]={x,y};
}
}
}
}
}
return res;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
memset(st,0,sizeof st);
for(int i=0;i<n;i++)
cin>>g[i];
cout<<bfs(n,m)<<endl;
}
return 0;
}