Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
0
Indexable
Never
#include <iostream>

using namespace std;
int n;
int map[101][101];
int kq[101][101];
int dem[6];
int visit[101][101];
int visit0[101][101];
int qx[10001], qy[10001];
int qx1[10001], qy1[10001];

int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
void reset(){
	for(int i =0; i<n; i++){
		for(int j =0; j<n; j++){
			visit[i][j] = 0;
		}
	}
	for(int i=0; i<6; i++) dem[i] = 0;
}

void dienkq(int a){
	for(int i =0; i<n; i++){
		for(int j =0; j<n; j++){
			if(visit0[i][j] && kq[i][j] == 0) kq[i][j] = a  ;
		}
	}
}
int timmax(){
	int x=0;
	int index=0;
	for(int i=1; i<6; i++) {
		if(x <= dem[i]) x=dem[i], index = i;
	}
	return index;
}

void bfs(int a, int b, int giatri){
	int front = 0; int rear = 0;
	qx1[rear] = a; 
	qy1[rear] = b; 
	rear ++;
	visit[a][b] = 1;
	dem[giatri]++;
	while(front != rear){
		int temx = qx1[front];
		int temy = qy1[front];
		front ++;
		for(int i =0; i<4; i++){
			int xx = temx + dx[i];
			int yy = temy + dy[i];
			if(xx >=0 && yy >=0 && xx <n && yy <n && !visit[xx][yy] ){
				if(map[xx][yy] == giatri){
					visit[xx][yy] = 1;
					dem[giatri]++;
					qx1[rear] = xx ;
					qy1[rear] = yy; 
					rear ++;
				}
			}
		}
	}
}
void xuly(int a, int b){
	int front = 0; int rear = 0;
	qx[rear] = a; 
	qy[rear] = b; 
	rear ++;
	visit[a][b] = 1;
	dem[0] ++;
	visit0[a][b] =1;
	while(front != rear){
		int temx = qx[front];
		int temy = qy[front];
		front ++;
		for(int i =0; i<4; i++){
			int xx = temx + dx[i];
			int yy = temy + dy[i];
			if(xx >=0 && yy >=0 && xx <n && yy <n && !visit[xx][yy] ){
				if(map[xx][yy] == 0){
					visit[xx][yy] = 1;
					visit0[xx][yy] = 1;
					dem[0]++;
					qx[rear] = xx ;
					qy[rear] = yy; 
					rear ++;
				}
				else{
					bfs(xx, yy, map[xx][yy]);
				}
			}
		}
	}

}

int main(){
	freopen("Text.txt", "r", stdin);
	int tc; cin >>tc;
	for(int t = 1; t<=tc; t++){
		cin >> n ;
		for(int i =0; i<n; i++){
			for(int j =0; j<n; j++){
				cin >>map[i][j];
				visit0[i][j] = 0;
				kq[i][j] = map[i][j];
			}
		}
		for(int i =0; i<n; i++){
			for(int j =0; j<n; j++){
				if(map[i][j] == 0 && visit0[i][j] == 0){
					reset();
					xuly(i, j);
					int a = timmax();
					dienkq(a);
				}
			}
		}
		//dien kq vao map
		for(int i =0; i<n; i++){
			for(int j =0; j<n; j++) map[i][j] = kq[i][j];
		}
		int ans = 0;
		reset();
		for(int i =0; i<n; i++){
			for(int j = 0; j<n; j++){
				//cout <<map[i][j]<<" ";
				if(visit[i][j] == 0){
					bfs(i, j, map[i][j]);
					ans ++;
				}
			}
			//cout <<endl;
		}
		cout <<"Case #"<< t << endl << ans << endl;
	}

	return 0;
}