全re求救，样例过了

P1162 填涂颜色

xwx123456 @ 2023-12-16 16:44:10

#include <bits/stdc++.h>
using namespace std;
int a[35][35];
int bx[4]= {1,-1,0,0},by[4]= {0,0,1,-1},n;
struct node {
    int x,y;
};
queue<node> q;
int bfss(int x1,int y1) {
    q.push({x1,y1});
    a[x1][y1]=2;
    while(!q.empty()) {
        int xx=q.front().x,yy=q.front().y;
        q.pop();
        for(int i=0; i<4; i++) {
            int nx=xx+bx[i],ny=yy+by[i];
            if(nx<1||nx>n||ny<1||ny>n||a[nx][ny]!=0) {
                continue;
            }
            q.push({nx,ny});
            a[nx][ny]=2;
        }
    }
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin>>a[i][j];
        }
    }
    int x1,y1,flag=0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(a[i][j]==1&&flag==0) {
                x1=i;
                y1=j;
                flag=1;
            }
        }
    }
    bfss(x1+1,y1+1);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

by zhangxisu @ 2023-12-16 17:00:07

emmmm，如果BFS过不了，可以试试DFS,类似这样:

void dfs(int x,int y)
{
    for(int i=0;i<=3;i++)
    {
        ...//移动
    }
    return;
}

再说说思路，可以反向思考，填1里面很难，那就把矩阵外面填充为-1（别忘了备份原矩阵），然后判断，不是1，不是-1，那就添2 此题 n≤30 ,完全没问题。

by zhangxisu @ 2023-12-16 17:03:27

@zhangxisu 可以这么做是因为1围成的是环，不论如何都能把外圈遍历，类似这样：

cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[1][i]==0) ...;
        if(a[n][i]==0) ...;
        if(a[i][1]==0) ...;
        if(a[i][n]==0) ...;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ...
        }
        ...
    }

by hdkk @ 2023-12-16 17:24:26

@xwx123456 你bfss函数没返回值，可以改成void或者加个return 0;

by xwx123456 @ 2023-12-16 18:08:29

@zhangxisu @hdkk 已AC

by hskjmhek @ 2023-12-27 13:16:55

efmsa

|