4\5 RE all the time QAQ

P1162 填涂颜色

今夕何年 @ 2022-05-12 21:39:12

4\5调试了一万遍,始终RE,在本地编译器输出中间过程发现首先用bfs填充边框的时候一直有几个点没填充,将数组row开大一点本地能过,但是为什么会开这么大?(大概1000,点4答案能过,但是时间超限了),求dalao,%%%%%%%%

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<limits.h>
using namespace std;

struct def_point{
    int x,y;
}; 
bool ck[32][32];
int mp[32][32];
int ans[32][32];
int n;

void bfs(int x,int y,int val=1){//从x,y开始进行搜索,填充值默认为val=1 
    int st=0,ed=1;//头,尾
    def_point row[300]; //在本地编译运行时,row开大一些(1000)测试点4答案是对的
    int dir_x[4]={0,0,-1,1};
    int dir_y[4]={-1,1,0,0};//方向数组上下左右
    memset(row,0,sizeof(row));
    //初始化 
    row[ed].x=x;row[ed].y=y; //首个元素入队 
    ++ed;
    while(st!=ed){
        ++st;
        mp[row[st].x][row[st].y]=val;
        if(val==2)ans[row[st].x][row[st].y]=val;
        for(int i=0;i<=3;++i){
            if( (row[st].x+dir_x[i])>0   &&//不越界且临近点属于搜寻点 
                (row[st].x+dir_x[i])<=n  &&//则将该点加入到队列row中 
                (row[st].y+dir_y[i])>0   &&
                (row[st].y+dir_y[i])<=n  &&
                (ck[row[st].x+dir_x[i]][row[st].y+dir_y[i]])  &&
                (mp[row[st].x+dir_x[i]][row[st].y+dir_y[i]]==0) ){
                    ck[row[st].x+dir_x[i]][row[st].y+dir_y[i]]==false;
                    row[ed].x=row[st].x+dir_x[i];
                    row[ed].y=row[st].y+dir_y[i];
                    ++ed; 
                }
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>mp[i][j];
            ans[i][j]=mp[i][j];
        }
    }
    memset(ck,true,sizeof(ck));
    for(int i=1;i<=n;++i){
        if(mp[1][i]==0)bfs(1,i);
        if(mp[n][i]==0)bfs(n,i);
        if(mp[i][1]==0)bfs(i,1);
        if(mp[i][n]==0)bfs(i,n);
    }
    for(int i=2;i<=n-1;++i){
        for(int j=2;j<=n-1;++j){
            if(mp[i][j]==0)bfs(i,j,2);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
} 

by 今夕何年 @ 2022-05-12 21:41:26

思想就是存一个方阵副本ans,先bfs用1填充外围的0,这样只剩下内部圈起来的0,第二次bfs用2填充时,将填充的同样操作让副本同样操作,这样ans就是只填充了2,没有填充1


by 今夕何年 @ 2022-05-13 19:42:50

对不起占用大家时间了QAQ 自己debug了,原来是

ck[row[st].x+dir_x[i]][row[st].y+dir_y[i]]==false;

多打了个=,好好的赋值变逻辑运算QAQ 蒟蒻菜死了


by 今夕何年 @ 2022-05-13 19:43:25

然后数据范围开【900】就好。。。


|