Đặng Hà Mi
@hamii_1308
Viet Nam, Hà Nội
Joined Feb 2019
World Rank: #117579 (0 points)
Institution: Ha Noi University of Industrial
#include <iostream> using namespace std; const int maxn = 1e4 + 2; int tc, n; int a[maxn][maxn], check[maxn][maxn], check2[maxn][maxn]; struct point { int x, y; }; bool isOk(point t) { return 0 <= t.x && t.x < n && 0 <= t.y && t.y < n; } void ShowMatrix(int ma[][maxn]) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << ma[i][j] << " "; } cout << endl; } cout << "------------" << endl; } int X[4] = {0, 0, 1, -1}; int Y[4] = {-1, 1, 0, 0}; int S[6] = {0, 1, 2, 3, 4, 5}; int ListS[maxn * 10000]; void dfs(point t, int cNum) { for (int i = 0; i < 4; i++) { point t1; t1.x = t.x + X[i]; t1.y = t.y + Y[i]; if (isOk(t1) && (a[t1.x][t1.y] == a[t.x][t.y] || a[t.x][t.y] == 0) && check[t1.x][t1.y] != cNum && check[t1.x][t1.y] != -cNum) { if (a[t1.x][t1.y] != 0) { S[a[t1.x][t1.y]]++; check[t1.x][t1.y] = -cNum; } else check[t1.x][t1.y] = cNum; dfs(t1, cNum); } } } void dfs2(point t, int cNum) { for (int i = 0; i < 4; i++) { point t1; t1.x = t.x + X[i]; t1.y = t.y + Y[i]; if (isOk(t1) && a[t1.x][t1.y] == a[t.x][t.y] && check2[t1.x][t1.y] == 0) { check2[t1.x][t1.y] = cNum; dfs2(t1, cNum); } } } int getMaxS(int S[]) { int ans = 0, res = 0; for (int i = 1; i < 6; i++) if (ans <= S[i]) ans = S[i], res = i; return res; } void resetS(int S[]) { for (int i = 1; i < 6; i++) S[i] = 0; } int main() { freopen("test.txt", "r", stdin); cin >> tc; for (int ic = 1; ic <= tc; ic++) { cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> a[i][j]; check[i][j] = 0; check2[i][j] = 0; } int cNum = 1; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (check[i][j] == 0 && a[i][j] == 0) { check[i][j] = cNum; point t; t.x = i, t.y = j; dfs(t, cNum); ListS[cNum++] = getMaxS(S); resetS(S); } } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] == 0) a[i][j] = ListS[check[i][j]]; cout << "Case #" << ic << endl; int ans = 1; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (check2[i][j] == 0) { check2[i][j] = ans; point t; t.x = i, t.y = j; dfs2(t, ans++); } cout << ans - 1 << endl; // ShowMatrix(a); } return 0; }
RSS