khuvucsoltu
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