Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
2.3 kB
2
Indexable
Never
#include<iostream>
using namespace std;

int mover[4]={-1,0,1,0};
int movec[4]={0,1,0,-1};

struct point{
	int x,y;
};

class queue{
	int rear,front;
	point arr[1000000];
public:
	queue(){
		rear=front=-1;
	}
	void push(point a){
		rear++;
		arr[rear]=a;
	}
	point pop(){
		front++;
		return arr[front];
	}
	bool isempty(){
		return (rear==front);
	}
	void reset(){
		rear=front=-1;
	}
	point peek(){
		return arr[front+1];
	}
};

queue q1,q2;
int t,n;
int mang[100][100];
int tansuat[6];
bool visit[100][100]; 

void resettansuat(){
	for(int i=1;i<=5;i++) tansuat[i]=0;
}

void bfs0(int a, int b){
	q1.reset(); q2.reset();
	visit[a][b]=true;
	point s={a,b};
	q1.push(s); q2.push(s);
	while(!q1.isempty()){
		point u=q1.pop();
		for(int h=0;h<4;h++){
			int nx=u.x+mover[h]; int ny=u.y+movec[h]; point v={nx,ny};
			if(nx>=0 && ny>=0 && nx<n && ny<n && !visit[nx][ny] && mang[nx][ny]==0) {
				visit[nx][ny]=true;
				q1.push(v); q2.push(v);
			}
		}
	}
}

void bfske(){
	while(mang[q2.peek().x][q2.peek().y]==0){
		point u=q2.pop();
		for(int h=0;h<4;h++){
			int nx=u.x+mover[h]; int ny=u.y+movec[h]; point v={nx,ny};
			if(nx>=0 && ny>=0 && nx<n && ny<n && !visit[nx][ny] && mang[nx][ny]!=0) {
				visit[nx][ny]=true;
				tansuat[mang[nx][ny]]++;
				q2.push(v);
			}
		}
	}
}

void bfs(){
	while(!q2.isempty()){
		point u=q2.pop();
		for(int h=0;h<4;h++){
			int nx=u.x+mover[h]; int ny=u.y+movec[h]; point v={nx,ny};
			if(nx>=0 && ny>=0 && nx<n && ny<n && mang[nx][ny]==mang[u.x][u.y] && !visit[nx][ny] ){
				visit[nx][ny]=true;
				q2.push(v);
				tansuat[mang[nx][ny]]++;
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> n;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) {
				cin >> mang[i][j];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(!visit[i][j] && mang[i][j]==0){
					bfs0(i,j);
					resettansuat; bfske(); bfs();
					int max=-1; int index=0;
					for(int k=1;k<=5;k++){
						if(tansuat[k]>=max){
							max=tansuat[k];
							index=k;
						}
					}
					for(int a=0;a<n;a++){
						for(int b=0;b<n;b++){
							if(visit[a][b] && mang[a][b]==0) mang[a][b]=index;
						}
					}
				}
			}
		}
	}


	return 0;
}
Leave a Comment