// 算法竞赛->第3章->3.2 #include <cstdio> #include <utility> #include <cstring> #include <algorithm> #include <functional> #define max(a, b) (((a) > (b)) ? (a) : (b)) bool row_visit[10][10]; bool col_visit[10][10]; bool group_vis[10][10]; std::pair<int, int> pii[10]; int pos[10], line[20]; int mp[10][10]; int score[10][10] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 6, 6, 6, 6, 6, 6, 6, 6, 6}, {0, 6, 7, 7, 7, 7, 7, 7, 7, 6}, {0, 6, 7, 8, 8, 8, 8, 8, 7, 6}, {0, 6, 7, 8, 9, 9, 9, 8, 7, 6}, {0, 6, 7, 8, 9, 10, 9, 8, 7, 6}, {0, 6, 7, 8, 9, 9, 9, 8, 7, 6}, {0, 6, 7, 8, 8, 8, 8, 8, 7, 6}, {0, 6, 7, 7, 7, 7, 7, 7, 7, 6}, {0, 6, 6, 6, 6, 6, 6, 6, 6, 6}}; long long ans; void dfs(int x, int y) { if(y == 10) {dfs(line[pos[x] + 1], 1); return ;} if(x == 0) { long long sum = 0; for(int i = 1; i <= 9; i++) { for(int j = 1; j <= 9; j++) { sum += score[i][j] * mp[i][j]; } } ans = max(ans, sum); return ; } if(mp[x][y] != 0) {dfs(x, y + 1); return ;} for(int i = 1; i <= 9; i++) { int in_group = ((x - 1) / 3) * 3 + (y - 1) / 3 + 1; if(row_visit[x][i] || col_visit[y][i] || group_vis[in_group][i]) continue; row_visit[x][i] = true; col_visit[y][i] = true; group_vis[in_group][i] = true; mp[x][y] = i; dfs(x, y + 1); row_visit[x][i] = false; col_visit[y][i] = false; group_vis[in_group][i] = false; mp[x][y] = 0; } } int main() { for(int i = 1; i <= 9; i++) { pii[i].second = i; pii[i].first = 0; for(int j = 1; j <= 9; j++) { scanf("%d", &mp[i][j]); if(mp[i][j] != 0) { int in_group = ((i - 1) / 3) * 3 + (j - 1) / 3 + 1; row_visit[i][mp[i][j]] = true; col_visit[j][mp[i][j]] = true; group_vis[in_group][mp[i][j]] = true; pii[i].first++; } } } std::sort(pii + 1, pii + 10, std::greater<std::pair<int, int>>()); for(int i = 1; i <= 9; i++) { line[i] = pii[i].second; pos[pii[i].second] = i; } dfs(line[1], 1); if(ans == 0) puts("-1"); else printf("%lld", ans); return 0; }