1 条题解
-
1
#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
- 上传者