4\5 RE all the time QAQ
查看原帖
4\5 RE all the time QAQ
122342
今夕何年楼主2022/5/12 21:39

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;
} 
2022/5/12 21:39
加载中...