1 条题解

  • 1
    @ 2025-1-27 15:56:34
    #include <bits/stdc++.h>
    using namespace std;
    int a[9][9];
    bool vish[9][10];//vish[i][k] 第i行里面数字k有没有用 
    bool visl[9][10];//visl[i][k] 第i列里面数字k有没有用
    bool vis[3][3][10];//vis[i][j][k]  在第i行j列的大九宫格里数字k有没有用 
    
    void p(){
    	for(int i=0;i<=8;i++){
    		for(int j=0;j<=8;j++){
    			cout<<a[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    	cout<<endl;
    }
    
    bool flag=false;
    
    void dfs(int k){//给k号格子填写数字
    	if(flag==true) return;
    	if(k==81){//到头了 
    		flag=true;
    		p();
    		return ;
    	}
    	int x=k/9;
    	int y=k%9;
    	//k号格子 在x行 y列
    	int tx=x/3;
    	int ty=y/3;
    	//这个格子隶属于 第tx行 ty列的大九宫格
    	if(a[x][y]!=0){//这个格子不用填 
    		dfs(k+1); 
    	}else{
    		for(int i=1;i<=9;i++){//尝试1到9的填写 
    			if(vish[x][i]==0&&visl[y][i]==0&&vis[tx][ty][i]==0){
    			//x行不能重复 y列不能重复 tx,ty这个九宫格不能重复 
    				vish[x][i]=1;
    				visl[y][i]=1;
    				vis[tx][ty][i]=1;
    				a[x][y]=i;
    				dfs(k+1);
    				a[x][y]=0;
    				vish[x][i]=0;
    				visl[y][i]=0;
    				vis[tx][ty][i]=0;	
    			} 
    		}
    	}
    	 
    }
    
    int main(){
    	for(int i=0;i<=8;i++){
    		for(int j=0;j<=8;j++){
    			cin>>a[i][j];
    			if(a[i][j]!=0){
    				int tx=i/3;
    				int ty=j/3;
    				vish[i][a[i][j]]=1;
    				visl[j][a[i][j]]=1;
    				vis[tx][ty][a[i][j]]=1;	
    			}
    		}
    	}
    	dfs(0);
    }
    
    
    
    • 1

    信息

    ID
    81
    时间
    1000~5000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    3
    已通过
    1
    上传者