今夕何年 @ 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】就好。。。