Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.4 kB
1
Indexable
Never
#include<iostream>
using namespace std;
int N;
int A[105][105];
int visit[105][105];
int A_copy[105][105];
int vuongquoc[6];
int f=-1, r=-1;
int Qx[10000000];
int Qy[10000000];
int dx[4]= {1,-1,0,0};
int dy[4]={0,0,1,-1};
void push(int x, int y)
{
	f++;
	Qx[f] =x;
	Qy[f] =y;
}
void pop(int &x, int &y)
{
	r++;
	x= Qx[r];
	y=Qy[r];
}
void reset()
{
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			visit[i][j] =0;
		}
	}
	for(int i=0; i<6; i++)
	{
		vuongquoc[i] =0;
	}
}

void bfs_vung(int x,int y)
{
	push(x,y);
	visit[x][y] =1;
	while(f != r)
	{
		pop(x,y);
		for(int i=0; i<4; i++)
		{
			int xx= x+dx[i];
			int yy= y+dy[i];
			if(xx >=1 && xx <=N && yy>=1 && yy<=N && visit[xx][yy] ==0 && A_copy[xx][yy] == A_copy[x][y]){
				push(xx,yy);
				visit[xx][yy]=1;
			}
		}
	}
}

void bfs(int x,int y)
{
	push(x,y);
	visit[x][y] =1;
	while(f != r)
	{
		pop(x,y);
		for(int i=0; i<4; i++)
		{
			int xx= x+dx[i];
			int yy= y+dy[i];
			if(xx >=1 && xx <=N && yy>=1 && yy<=N && visit[xx][yy] ==0 ){
				if((A[x][y] ==0 ) || (A[x][y] != 0 && A[xx][yy] == A[x][y])){
					push(xx,yy);
					//cout << xx << " " << yy << endl;
					vuongquoc[A[xx][yy]] ++;
					visit[xx][yy] =1;
				}
			}
		}
	}

}
int main()
{
	int t;
	cin >> t;
	for(int stt=1; stt <=t; stt++)
	{
		cin >>N;
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				cin >> A[i][j];
				A_copy[i][j] = A[i][j];
			}
		}
		/////////////////////
		for(int i=1; i<= N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				/////////////////////////
				if(A_copy[i][j] ==0 ){
					//cout << " hi" << i << " " << j << endl;
					reset();
					bfs(i,j);
					int maxx=0;
					int a=0;
					for(int i=5; i>0; i--){
						if(vuongquoc[i] > maxx){ maxx= vuongquoc[i]; a=i; }
						//cout << a << endl;
					}
					///////////
					for(int row=1; row <=N; row ++)
					{
						for(int col=1; col <=N; col ++)
						{
							if(visit[row][col] ==1 && A[row][col] == 0){
								A_copy[row][col]=a;
							}
						}
					}
				}
				///////////////////////////////////////
			}
		
		}
		
		int count_ =0;
		reset();
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				if(visit[i][j] == 0)
				{
					bfs_vung(i,j);
					count_ ++;
				}			
			}
		}
		cout << "Case #"<< stt << endl << count_ << endl;
	}
}