dfxgbm @ 2021-04-16 18:39:21
#include <cstdio>
#include <algorithm>
#include <queue>
#define noexced(x,y) (x>=0&&y>=0&&x<n&&y<n)
#define border(x,y) (x==0||y==0||x==n-1||y==n-1)
const int M=31,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
using namespace std;
short int g[M][M];
bool vis[M][M];
typedef struct {
int x,y;
}node;
int n,minrow[M],maxrow[M],mincol[M],maxcol[M];
int bfs(queue<node> q) {
int cnt=1;
while(!q.empty()) {
node now=q.front();
for(int i=0;i<4;i++) {
int nx=now.x+dx[i],ny=now.y+dy[i];
if(!vis[nx][ny]&&(noexced(nx,ny))&&g[nx][ny]==0) {
node New;
New.x=nx,New.y=ny;
vis[nx][ny]=1;
cnt++;
q.push(New);
}
}
q.pop();
}
return cnt;
}
// 边界存在连通块则不闭合
bool closed(void) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(vis[i][j]&&border(i,j)) {
return 0;
}
}
}
return 1;
}
int main(){
//bool closed[M][M];
queue<node> q;
scanf("%d",&n);
for(int i=0;i<n;i++) {
//fill(closed[i],closed[i]+n+1,0);
for(int j=0;j<n;j++) {
scanf("%d",&g[i][j]);
}
}
for(int i=1;i<n-1;i++) {
for(int j=1;j<n-1;j++) {
if(g[i][j]==0&&!vis[i][j]) {
node fst;
fst.x=i,fst.y=j;
vis[i][j]=1;
q.push(fst);
bfs(q);
if(!closed()) { //如果不封闭
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(vis[i][j]) vis[i][j]=0;
}
}
}
else {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(vis[i][j]) g[i][j]=2;
}
}
}
}
}
}
for(int i=0;i<n;i++) {
printf("%d",g[i][0]);
for(int j=1;j<n;j++) {
printf(" %d",g[i][j]);
}
putchar('\n');
}
return 0;
}
by chenhongyu20100506 @ 2021-10-17 21:41:03
#include<bits/stdc++.h>
using namespace std;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0},cnt,n,m;
char ch[120][120];
bool f[120][120];
void dfs(int r,int c){
for(int i=0;i<4;i++){
int nr=r+dx[i];
int nc=c+dy[i];
if(1<=nr&&nr<=n&&1<=nc&&nc<=m&&ch[nr][nc]>='1'&&ch[nr][nc]<='9'&&!f[nr][nc]){
f[nr][nc]=true;
dfs(nr,nc);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ch[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(ch[i][j]>='1'&&ch[i][j]<='9'&&!f[i][j]){
cnt++;
f[i][j]=true;
dfs(i,j);
}
}
}
cout<<cnt;
return 0;
}