Sudoku Killer
原题链接https://vjudge.net/contest/345248#problem/P
就是写出一个程序来算数独
数独是要求行列以及每个小九宫格内的数字都不能相同
所以我们用dfs来试所有的情况
用三个二维数组来记录数字是否重复使用
visx[x][当前数]；判断行是否使用过
visy[y][当前数]；判断列是否使用过
visz[x/3*3+y/3][当前数]判断九宫格内是否使用过（每行列三个数压缩到一个位置的数组，再由二维确定具体数是否使用过）
本题还要注意输入输出的情况~~，唔，很烦人的输入输出~~
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
long long vis[9][10];//地图
long long visx[9][10];//行
long long visy[9][10];//列
long long visz[9][10];//九宫格
long long p;
long long c;
void output()//输出
{long long i,j;if(c!=0){printf("\n");}for(i=0; i<9; i++){for(j=0; j<9; j++){if(j==0){printf("%lld",vis[i][j]);}else{printf(" %lld",vis[i][j]);}}printf("\n");c++;}
}
void dfs(long long x,long long y)//遍历
{long long i,j;
// printf("***********\n");if(p==1)//已经得到结果 跳出{return ;}else if(x==9&&y==0)//全部位置跑完{output();p=1;return ;}else if(y==9)//行跑完换到下一行{// printf("******************\n");dfs(x+1,0);}else if(vis[x][y]!=0)//换到下一格{dfs(x,y+1);}else if(vis[x][y]==0)//尝试当前位置{for(i=1; i<=9; i++){if(visx[x][i]==1||visy[y][i]==1||visz[x/3*3+y/3][i]==1){continue;}if(p==1){return ;}// printf("x=%lld %lld %lld*\n",x,i,visx[x][i]);// printf("y=%lld %lld %lld*\n",y,i,visy[y][i]);// printf("z=%lld %lld %lld*\n",x/3*3+y/3,i,visz[x/3*3+y/3][i]);vis[x][y]=i;visx[x][i]=1;visy[y][i]=1;visz[x/3*3+y/3][i]=1;dfs(x,y+1);//进入下一位置if(p==1){return ;}vis[x][y]=0;visx[x][i]=0;visy[y][i]=0;visz[x/3*3+y/3][i]=0;// printf("x=%lld %lld %lld**\n",x,i,visx[x][i]);// printf("y=%lld %lld %lld**\n",y,i,visy[y][i]);// printf("z=%lld %lld %lld**\n",x/3*3+y/3,i,visz[x/3*3+y/3][i]);}}
}
int main()
{long long n,m,i,j,z,c=0;char s[2];//输入swhile(~scanf("%s",s))//第一行第一个{memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));memset(visz,0,sizeof(visz));p=0;if(s[0]=='?'){vis[0][0]=0;}else{vis[0][0]=s[0]-'0';visx[0][vis[0][0]]=1;visy[0][vis[0][0]]=1;visz[0/3*3+0/3][vis[0][0]]=1;}for(j=1; j<9; j++)//第一行后8个{scanf("%s",&s);if(s[0]=='?'){vis[0][j]=0;}else{vis[0][j]=s[0]-'0';visx[0][vis[0][j]]=1;visy[j][vis[0][j]]=1;visz[0/3*3+j/3][vis[0][j]]=1;}}for(i=1; i<9; i++)//剩下8行{for(j=0; j<9; j++){scanf("%s",s);if(s[0]=='?'){vis[i][j]=0;}else{vis[i][j]=s[0]-'0';visx[i][vis[i][j]]=1;visy[j][vis[i][j]]=1;visz[i/3*3+j/3][vis[i][j]]=1;}}}/*for(i=0; i<9; i++){for(j=0; j<9; j++){printf("%lld ",vis[i][j]);}printf("\n");}*/// printf("\n");dfs(0,0);//遍历}return 0;
}