1 条题解
-
0
#include<bits/stdc++.h> //#define int long long using namespace std; const int N = 10; const int inf = 0x3f3f3f3f; int a[N][N]; int maxx = -inf; bool ch = false; bool hqt[N][N];//表示第i宫中是否存在j bool hang[N][N];//表示第i行中是否存在j bool lie[N][N];//表示第i列中是否存在j const int f[N][N] = { {6, 6, 6, 6, 6, 6, 6, 6, 6}, {6, 7, 7, 7, 7, 7, 7, 7, 6}, {6, 7, 8, 8, 8, 8, 8, 7, 6}, {6, 7, 8, 9, 9, 9, 8, 7, 6}, {6, 7, 8, 9, 10, 9, 8, 7, 6}, {6, 7, 8, 9, 9, 9, 8, 7, 6}, {6, 7, 8, 8, 8, 8, 8, 7, 6}, {6, 7, 7, 7, 7, 7, 7, 7, 6}, {6, 6, 6, 6, 6, 6, 6, 6, 6} }; bool check(int i , int j , int num){ return hqt[i / 3 * 3 + j / 3][num] == false && hang[i][num] == false && lie[j][num] == false; } int m; struct node{ int x , y; }; node k[N*N]; void dfs(int step , int ans){ // cout << h << " " << sum << endl; if(step >= m + 1){ ch = true; maxx = max(maxx , ans); return; } for(int j = 1 ; j <= 9; j ++){//数 if(check(k[step].x , k[step].y , j)){ hqt[k[step].x / 3 * 3 + k[step].y / 3][j] = true; hang[k[step].x][j] = true; lie[k[step].y][j] = true; dfs(step + 1 , ans + j * f[k[step].x][k[step].y]); hqt[k[step].x / 3 * 3 + k[step].y / 3][j] = false; hang[k[step].x][j] = false; lie[k[step].y][j] = false; } } } //int change(int x1 , int x2 , int y1 , int y2){ // int ans = 0; // for(int i = y1 ; i <= y2 ; i ++){ // ans += a[x1][i] - '0'; // ans += a[x2][i] - '0'; // } //// return ans; // for(int i = x1 + 1 ; i < x2 ; i ++){ // ans += a[i][y1] - '0'; // ans += a[i][y2] - '0'; // } // return ans; //} signed main(){ freopen("tower.in" , "r" , stdin); freopen("tower.out" , "w" , stdout); int t = 0; for(int i = 0 ; i < 9 ; i ++){ for(int j = 0 ; j < 9 ; j ++){ cin >> a[i][j]; if(a[i][j] != 0){ hqt[i / 3 * 3 + j / 3][a[i][j]] = true; hang[i][a[i][j]] = true; lie[j][a[i][j]] = true; t += a[i][j] * f[i][j]; }else{ m ++; k[m].x = i; k[m].y = j; } } } dfs(1 , t); if(ch){ cout << maxx; }else{ cout << "-1"; } return 0; }
信息
- ID
- 551
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 115
- 已通过
- 14
- 上传者