2 条题解

  • 1
    @ 2025-7-25 9:48:32
    #include<bits/stdc++.h>
    //#define int long long
    using namespace std;
    const int N = 10;
    const int inf = 0x3f3f3f3f;
    char a[N][N];
    bool hqt[N][N];//表示第i宫中是否存在j 
    bool hang[N][N];//表示第i行中是否存在j 
    bool lie[N][N];//表示第i列中是否存在j 
    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];
    bool dfs(int step){
    //	cout << h << " " << sum << endl;
    	if(step >= m+1){
    		return true;
    	}
    	for(int j = 1 ; j <= 9; j ++){//数 
    		if(check(k[step].x , k[step].y , j)){
    			
    			a[k[step].x][k[step].y] = (char)(j + '0');
    				
    			hqt[k[step].x / 3 * 3 + k[step].y / 3][j] = true;
    			hang[k[step].x][j] = true;
    			lie[k[step].y][j] = true;
    					
    			if(dfs(step + 1)) return true;
    			
    				
    			hqt[k[step].x / 3 * 3 + k[step].y / 3][j] = false;
    			hang[k[step].x][j] = false;
    			lie[k[step].y][j] = false;
    		} 
    	}
    	return false;
    	
    	
    	
    }
    
    signed main(){
    	freopen("number.in" , "r" , stdin);
    	freopen("number.out" , "w" , stdout);
    	for(int i = 0 ; i < 9 ; i ++){
    		for(int j = 0 ; j < 9 ; j ++){
    			cin >> a[i][j];
    			if(a[i][j] != '*'){
    				hqt[i / 3 * 3 + j / 3][(int)(a[i][j] - '0')] = true;
    				hang[i][(int)(a[i][j] - '0')] = true;
    				lie[j][(int)(a[i][j] - '0')] = true;
    			}else{
    				m ++;
    				k[m].x = i;
    				k[m].y = j;
    			}
    		}
    	}
    	if(dfs(1)){
    		for(int i = 0 ; i < 9 ; i ++){
    				for(int j = 0 ; j < 9 ; j ++){
    					cout << a[i][j] << " ";
    				}
    				cout << endl;
    		}
    	}
    	
    	return 0;
    }
    

    信息

    ID
    550
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    89
    已通过
    28
    上传者