khuvucsoltu

 avatar
quoc14
c_cpp
a month ago
3.8 kB
1
Indexable
Never
#include <iostream>

using namespace std;

int n;
int a[105][105], new_a[105][105];
int ans;
int visit0[105][105], visit1[105][105], visit2[105][105];
int cur;
int cur0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int tanso[105];
int max_tanso;
int max_vung;
bool inside(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n) {
		return true;
		
	}
	return false;
}

struct point {
	int x;
	int y;
};

point xungquanh[105];
point zero[105];

void resetvisit1() {
	for (int i = 0; i < 105; i++) {
		tanso[i] = 0;
		for (int j = 0; j < 105; j++) {
			visit1[i][j] = 0;
		}
	}
}

void resetvisit0() {
	
	for (int i = 0; i < 105; i++) {
		
		for (int j = 0; j < 105; j++) {
			visit0[i][j] = 0;
		}
	}
}

// lan0
void dfs1(int x, int y) {
	//cout << x << " " << y << endl;
	zero[++cur0].x = x;
	zero[cur0].y = y;
	visit0[x][y] = 1;
	
	for (int i = 0; i < 4; i++) {
		int x_next = x + dx[i];
		int y_next = y + dy[i];
		if (inside(x_next, y_next) && visit0[x_next][y_next] == 0) {
			if (a[x_next][y_next] == a[x][y]) {
				//cout << x_next << " " << y_next << endl;
				dfs1(x_next, y_next);
			}
			else {
				//cout << x_next << " " << y_next << endl;
				
				xungquanh[++cur].x = x_next;
				xungquanh[cur].y = y_next;
				//cout << cur << endl;
				//cout << xungquanh[cur].x << " " << xungquanh[cur].y << endl;
			}
		}
	}
	
}

// lan cac o xung quanh 0 de dem tanso
void dfs2(int x, int y) {
	
	visit1[x][y] = 1;
	tanso[a[x][y]] += 1;
	
	for (int i = 0; i < 4; i++) {
		int x_next = x + dx[i];
		int y_next = y + dy[i];
		
		if (inside(x_next, y_next) && visit1[x_next][y_next] == 0) {
			if (a[x_next][y_next] == a[x][y]) {
				dfs2(x_next, y_next);
			}
		}
		
	}
	
}

// lan tim vung sau khi update xong
void dfs3(int x, int y) {
	
	visit2[x][y] = 1;
	
	
	for (int i = 0; i < 4; i++) {
		int x_next = x + dx[i];
		int y_next = y + dy[i];
		
		if (inside(x_next, y_next) && visit2[x_next][y_next] == 0) {
			if (new_a[x_next][y_next] == new_a[x][y]) {
				dfs3(x_next, y_next);
			}
		}
		
	}
	
}

void solve(int testcase) {
	for (int i = 1; i < 105; i++) {
		for (int j = 1; j < 105; j++) {
			a[i][j] = 0;
			new_a[i][j] = 0;
		}
	}
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			new_a[i][j] = a[i][j];			
		}
	}
	resetvisit0();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			
			if (a[i][j] == 0 && visit0[i][j] == 0) {
				cur0 = 0;
				cur = 0;
				// lan 0 va luu cac o xung quanh 0
				dfs1(i, j);
				
				max_tanso = 0;
				max_vung = 0;
				resetvisit1();
				
				// dem tan so cac o xung quanh
				for (int i = 1; i <= cur; i++) {
					//cout << xungquanh[i].x << " " << xungquanh[i].y << " " << a[xungquanh[i].x][xungquanh[i].y] << endl;
					dfs2(xungquanh[i].x, xungquanh[i].y);
				}
				
				
				for (int i = 0; i <= 5; i++) {
					if (tanso[i] >= max_tanso) {
						max_tanso = tanso[i];
						max_vung = i;
					}
				}
				
				for (int i = 1; i <= cur0; i++) {
					new_a[zero[i].x][zero[i].y] = max_vung;
				}
			}
			
			
		}
	}
	ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit2[i][j] = 0;
		}
	}
	// lan cap nhat ans
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (visit2[i][j] == 0 && new_a[i][j] > 0) {
				ans++;
				dfs3(i, j);
			}
		}
	}
	
	
	
	cout << "Case #" << testcase << endl;
	cout << ans << endl;
	
}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;
	
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
	
}
Leave a Comment