1 条题解
-
0Guest LV 0 MOD
-
0
#include <bits/stdc++.h>//懒人专用头文件 #define inr int #define rpt(n) for(register int ttxyc=0;ttxyc<(n);++ttxyc)//宏定义 using namespace std; struct czakioi { int i, cnt; bool operator<(const czakioi cz)const { return cnt < cz.cnt; } } ioioi[10]; int hang[10][11], lie[10][11], gong[10][11], kkk[100][5], ans = -1, n, sum, u[10][10]; int findgong(int x, int y) { return x / 3 * 3 + y / 3; } int findscore(int x, int y) { if (x == 0 || x == 8 || y == 0 || y == 8) return 6; if (x == 1 || x == 7 || y == 1 || y == 7) return 7; if (x == 2 || x == 6 || y == 2 || y == 6) return 8; if (x == 3 || x == 5 || y == 3 || y == 5) return 9; return 10; } void dfs(int i, int now) { if (now + (n - i) * 90 <= ans) return; if (n == i) { if (ans < now) ans = now; return; } register int a = kkk[i][0], b = kkk[i][1], c = kkk[i][2], d = kkk[i][3]; for (register int num = 9; num > 0; --num) { if (hang[a][num] || lie[b][num] || gong[c][num]) continue; hang[a][num] = lie[b][num] = gong[c][num] = 1; dfs(i + 1, now + num * d); hang[a][num] = lie[b][num] = gong[c][num] = 0; } } main() { for (int i = 0; i < 9; ++i) { ioioi[i].i = i; for (int j = 0; j < 9; ++j) { int k; scanf("%d", &k); if (k) { hang[i][k] = lie[j][k] = gong[findgong(i, j)][k] = 1; sum += k * findscore(i, j); } else { ++ioioi[i].cnt; u[i][j] = 1; } } } sort(ioioi, ioioi + 9); for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) if (u[ioioi[i].i][j]) { kkk[n][0] = ioioi[i].i; kkk[n][1] = j; kkk[n][2] = findgong(kkk[n][0], j); kkk[n++][3] = findscore(kkk[n][0], j); } dfs(0, sum); printf("%d", ans); }/**/
- 1