1 条题解

  • 0
    @ 2025-7-25 9:47:28
    #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
    上传者