#include #define endl '\n' using namespace std; typedef vector > vvi; const int MAXN = 300 + 3; const int MAXD = 500 + 5; const int MAXP = 8 + 2; int n, d, p; int a[MAXN][MAXN]; int cnt[MAXP][MAXD]; vector best_evalutes(MAXP); vector evalute(vector > v) { vector ret(MAXD, 0); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!v[i][j]) return ret; cnt[a[i][j]][v[i][j]]++; } } for (int i = 1; i <= d; i++) { int best = 0; int maxi = -1; for (int j = 1; j <= p; j++) { if (cnt[j][i] > maxi) { maxi = cnt[j][i]; best = j; } } int cntMaxi = 0; for (int j = 1; j <= p; j++) if (cnt[j][i] == maxi) cntMaxi++; if (cntMaxi == 1) ret[best]++; } return ret; } vector > getSol1(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; if (i%2) sol[i][j] = x; else sol[i][n-j-1] = x; } } return sol; } vector > getSol1_1(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; if (i%2==0) sol[i][j] = x; else sol[i][n-j-1] = x; } } return sol; } vector > getSol2(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; for (int j = 0; j < n; j++) { for (int i = 0; i < n; i++) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; if (j%2) sol[i][j] = x; else sol[n-i-1][j] = x; } } return sol; } vector > getSol2_1(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; for (int j = 0; j < n; j++) { for (int i = 0; i < n; i++) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; if (j%2==0) sol[i][j] = x; else sol[n-i-1][j] = x; } } return sol; } vector > getSol3(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; int top = 0, bottom = n-1, L = 0, R = n-1; int ind = 0; while (L <= R) { for (int i = L; i <= R; i++) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; sol[top][i] = x; } top++; if (top > bottom) break; for (int i = top; i <= bottom; i++) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; sol[i][R] = x; } R--; if (L > R) break; for (int i = R; i >= L; i--) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; sol[bottom][i] = x; } bottom--; if (top > bottom) break; for (int i = bottom; i >= top; i--) { br++; if (br > n*n/d) br = 1, x++; if (x > d) x = 1; sol[i][L] = x; } L++; } return sol; } vector > getSol4(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; int R = 1; while (true) { } return sol; } vector > getSol5(int f = 1) { vector > sol(n); for (int i = 0; i < n; i++) sol[i].resize(n); int br = 0; int x = f; int step1, step2; if (d == 25) step1 = step2 = 60; else if (d == 50) step1 = 30, step2 = 60; else if (d == 120) step1 = 30, step2 = 25; else if (d == 240) step1 = 15, step2 = 25; else if (d == 500) step1 = 15, step2 = 12; else return sol; for (int I = 0; I < n; I += step1) { for (int J = 0; J < n; J += step2) { for (int i = 0; i < step1; i++) { for (int j = 0; j < step2; j++) { sol[I+i][J+j] = x; } } x++; } } return sol; } vector > v; vvi best[MAXP]; vector evalutes; void update() { for (int x = 1; x <= p; x++) { if (evalutes[x] > best_evalutes[x]) { best_evalutes[x] = evalutes[x]; best[x] = v; } } } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(42); clock_t start_time = clock(); freopen("gerrymandering.in", "r", stdin); freopen("gerrymandering.out", "w", stdout); cin >> n >> d >> p; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j]; v = getSol1(); for (int x = 1; x <= p; x++) best[x] = v; best_evalutes = evalute(v); v = getSol1_1(); evalutes = evalute(v); update(); v = getSol2(); evalutes = evalute(v); update(); v = getSol2_1(); evalutes = evalute(v); update(); v = getSol3(); evalutes = evalute(v); update(); v = getSol5(); evalutes = evalute(v); update(); // int iter = 1; // // while ((double)(clock() - start_time) / CLOCKS_PER_SEC < 4.2) // { // inter++; // // v = getSol1(iter); // evalutes = evalute(v); // // for (int x = 1; x <= p; x++) // { // if (evalutes[x] > best_evalutes[x]) // { // best_evalutes[x] = evalutes[x]; // best[x] = v; // } // } // // v = getSol2(iter); // evalutes = evalute(v); // // for (int x = 1; x <= p; x++) // { // if (evalutes[x] > best_evalutes[x]) // { // best_evalutes[x] = evalutes[x]; // best[x] = v; // } // } // } for (int x = 1; x <= p; x++) { cerr << "---" << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << best[x][i][j] << " "; cout << endl; } } return 0; } /** 5 5 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 */