AcWing 1613. 数独简单版
原题链接
简单
#include <iostream>
#include <cstring>
using namespace std;
const int N=10;
int n=9;
char g[N][N]; //存储原数独
int ans[N][N]; //存答案数独
//row每一行是否已使用过num;col每一列是否已使用过num;box每一个3*3是否已使用过num
bool row[N][N],col[N][N],box[3][3][N];
void dfs(int x,int y){
if(y==n){ //遍历到最后一列,该行遍历完,遍历下一行
y=0;
x++;
}
if(x==n){ //所有行遍历完,输出答案
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<ans[i][j];
}
cout<<endl;
}
return;
}
//(x,y)位置上有数字,跳过,处理下一个位置
if(g[x][y]!='.'){
dfs(x,y+1);
}
else{
//从1~9循环,找到符合条件的num
for(int num=1;num<=9;num++){
if(!row[x][num]&&!col[y][num]&&!box[x/3][y/3][num]){
ans[x][y]=num;
row[x][num]=col[y][num]=box[x/3][y/3][num]=true;
dfs(x,y+1); //递归下一个位置
row[x][num]=col[y][num]=box[x/3][y/3][num]=false; //回溯
}
}
}
}
int main(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>g[i][j];
if(g[i][j]!='.'){
int num=g[i][j]-'0'; //将字符转换为数字,存储到答案数组中
ans[i][j]=num;
row[i][num]=col[j][num]=box[i/3][j/3][num]=true; //将原始数独位置更新为true
}
}
}
dfs(0,0); //从第一个位置开始dfs遍历处理
return 0;
}