题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
char g[N][N];
bool vis[N][N];
typedef pair<int,int> PI;
queue<PI> q;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n;
int sum=0;
int res=0;
void bfs(int x,int y){
q.push({x,y});
res=0;
while(!q.empty()){
PI t=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=t.first+dx[i];
int yy=t.second+dy[i];
if(xx>=0&&xx<n&&yy>0&&yy<n&&g[xx][yy]=='#'&&!vis[xx][yy]){
vis[xx][yy]=true;
if(g[xx-1][yy]=='#'&&g[xx+1][yy]=='#'&&g[xx][yy-1]=='#'&&g[xx][yy+1]=='#'){
res=1;
}
q.push({xx,yy});
}
}
}
return ;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>g[i][j];
}
}
int t=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j]=='#'&&!vis[i][j]){
sum++;
bfs(i,j);
t+=res;
}
}
}
cout<<sum-t;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla