1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
| #include <bits/stdc++.h> #define rint register int using namespace std;
int a[10][10]; int w[10][10]; pair<int, int> tot[10]; int ord[15]; bool xx[10][10], yy[10][10], zz[10][10]; int ans = -1; int x_now; int x_final;
inline int get_z(int x, int y) { if (x <= 3) { if (y <= 3) return 1; if (y <= 6) return 2; else return 3; } else if (x <= 6) { if (y <= 3) return 4; if (y <= 6) return 5; else return 6; } else { if (y <= 3) return 7; if (y <= 6) return 8; else return 9; } }
inline void get_ans() { rint sum = 0; for (rint i = 1; i <= 9; ++i) { for (rint j = 1; j <= 9; ++j) { sum += a[i][j] * w[i][j]; } } ans = max(ans, sum); }
inline void get_nxt(int &x, int &y) { if (y == 9) y = 1, x = ord[x]; else ++y; }
void dfs(int x, int y) { if (a[x][y]) { if (x == x_final && y == 9) { get_ans(); } else { get_nxt(x, y); dfs(x, y); } } else { int xxx = x, yyy = y; get_nxt(xxx, yyy); for (rint i = 1; i <= 9; ++i) { if (xx[x][i] yy[y][i] zz[get_z(x, y)][i]) { continue; } xx[x][i] = yy[y][i] = zz[get_z(x, y)][i] = true; a[x][y] = i; if (x == x_final && y == 9) { get_ans(); } else { dfs(xxx, yyy); } a[x][y] = 0; xx[x][i] = yy[y][i] = zz[get_z(x, y)][i] = false; } } }
int main() { for (rint i = 1; i <= 9; ++i) { tot[i].second = i; for (rint j = 1; j <= 9; ++j) { scanf("%d", &a[i][j]); if (a[i][j] == 0) { ++tot[i].first; } else { xx[i][a[i][j]] = yy[j][a[i][j]] = zz[get_z(i, j)][a[i][j]] = true; } } } for (rint i = 1; i <= 9; ++i) { for (rint j = 1; j <= 9; ++j) { rint t = min(min(i, 9 - i + 1), min(j, 9 - j + 1)); if (t == 1) w[i][j] = 6; else if (t == 2) w[i][j] = 7; else if (t == 3) w[i][j] = 8; else if (t == 4) w[i][j] = 9; else if (t == 5) w[i][j] = 10; } } sort(tot + 1, tot + 10); for (rint i = 1; i <= 8; ++i) { ord[tot[i].second] = tot[i + 1].second; } x_now = tot[1].second; x_final = tot[9].second; dfs(x_now, 1); printf("%d", ans); return 0; }
|