题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010;
char a[N][N];
bool st[N][N];
int n;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> PII;
int count1=0; //表示有多少岛屿在未来不会被淹没
void bfs(int i,int j)
{
queue<PII> q;
queue<PII> p;
q.push({i,j});
p.push({i,j});
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(!st[x][y]&&a[x][y]=='#')
{
q.push({x,y});
p.push({x,y}); //把正在遍历的岛屿的所有点加入p中
st[x][y]=true;
}
}
}
while(p.size()) //找出该岛中是否有上下左右都是陆地的点
{
auto t=p.front();
p.pop();
int x=t.first,y=t.second;
if(a[x+1][y]=='#'&&a[x-1][y]=='#'&&a[x][y+1]=='#'&&a[x][y-1]=='#'&&x>1&&x<n&&y>1&&y<n)
{
count1++; //若有这样的点,则说明该岛屿未来不会被淹没
break;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
int count2=0; //标记总共有多少岛屿
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]=='#'&&!st[i][j])
{
bfs(i,j);
count2++;
}
}
}
cout<<count2-count1;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla