问一下为什么第四个点过不了

P1162 填涂颜色

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;
}

|