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;
    }
    
    • -1
      @ 2023-11-26 10:00:27
      #include<bits/stdc++.h>
      using namespace std;
      const int N = 10;
      int g[N][N], ans[N][N];
      int row[N][N], col[N][N], m[N][N];
      bool check(int x,int y, int t){
      	return !g[x][y] && !row[x][t] && !col[y][t] && !m[(x-1)/3*3 + (y-1)/3][t];
      }
      bool dfs(int x, int y){
      	if(g[x][y]){
      		if(y == 9){
      			if(dfs(x+1,1)) return true;
      		}else{
      			if(dfs(x,y+1)) return true;
      		}
      	}
      	if(x > 9){
      		for (int i = 1; i <= 9; i ++){
      			for(int j = 1; j <= 9; j ++){
      				cout << g[i][j] << " ";
      			}
      			cout << endl;
      		}
      		return true;
      	}
      	for(int i = 1; i <= 9; i ++){
      		if(check(x, y, i)){
      			row[x][i] = col[y][i] = m[(x-1)/3*3 + (y-1)/3][i] = true;
      			g[x][y] = i;
      			if(y == 9){
      				if(dfs(x+1,1)) return true;
      			}else{
      				if(dfs(x,y+1)) return true;
      			}
      			g[x][y] = 0;
      			row[x][i] = col[y][i] = m[(x-1)/3*3 + (y-1)/3][i] = false;
      		}
      	}
      	return false;
      }
      int main(){
      //	freopen("number.in","r",stdin);
      //	freopen("number.out","w",stdout);
      	for (int i = 1; i <= 9; i ++){
      		for (int j = 1; j <= 9; j ++){
      			char t;
      			cin >> t;
      			if(t == '*')
      				g[i][j] = 0;	
      			else{
      				g[i][j] = t - '0';
      				row[i][t-'0'] = col[j][t-'0'] = m[(i-1)/3*3 + (j-1)/3][t-'0'] = true;
      			}
      		}
      	}
      	dfs(1,1);
      	return 0;
      }
      
      • 1

      信息

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