比赛 EYOI常规赛 7th 评测结果 W
题目名称 数独2 最终得分 0
用户昵称 ムラサメ 运行时间 0.666 s
代码语言 C++ 内存使用 5.89 MiB
提交时间 2023-03-10 12:29:31
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int a[10][10];
bool h[10][10],l[10][10],g[10][10];
void print(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
        	cout<<a[i][j]<<" ";
		}
		cout<<endl;
    }
    exit(0);
}
void dfs(int x,int y){
    if(a[x][y]!=0){
        if(x==9&&y==9){
        	print();
		}
        if(y==9){
        	dfs(x+1,1);
		}
        else{
        	dfs(x,y+1);
		}
    }
    if(a[x][y]==0){
        for(int i=1;i<=9;i++){ 
            if(h[x][i]&&l[y][i]&&g[(x-1)/3*3+(y-1)/3+1][i]){
                a[x][y]=i;
                h[x][i]=false;
                l[y][i]=false;
                g[(x-1)/3*3+(y-1)/3+1][i]=false;
                if(x==9&&y==9){
                	print();
				}
                if(y==9){
                	dfs(x+1,1);
				}
				else{
					dfs(x,y+1);
				}
                a[x][y]=0;
                h[x][i]=true;
                l[y][i]=true;
                g[(x-1)/3*3+(y-1)/3+1][i]=true;
            }
        } 
    }
}
int main(){
	freopen("sudoku2.in","r",stdin);
	freopen("sudoku2.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(h,true,sizeof(h));
    memset(l,true,sizeof(l));
    memset(g,true,sizeof(g));
    char z;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
        	cin>>z;
        	if(z=='.'){
        		a[i][j]=0;
			}
			else{
				a[i][j]=int(z-'0');
			}
            if(a[i][j]>0){
                h[i][a[i][j]]=false;
                l[j][a[i][j]]=false;
                g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=false;
            }
        }
    } 
    dfs(1,1);
    return 0;
}