HDU 1426 数独
/*************************************************************************
> File Name: shudu.cpp
> Author:yuan
> Mail:
> Created Time: 2014年11月06日 星期四 14时35分05秒
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX=9;
int mat[MAX][MAX],ans[MAX][MAX];
int flag[10];
char c;
bool mark;
bool can1(int k,int num)
{
int x=k/9;
int y=k%9;
for(int i=0;i<9;i++)
if(ans[x][i]==num) return 0;
return 1;
}
bool can2(int k,int num)
{
int x=k/9;
int y=k%9;
for(int i=0;i<9;i++)
if(ans[i][y]==num) return 0;
return 1;
}
bool can3(int k,int num)
{
int x=k/9;
int y=k%9;
int sx=x/3*3,sy=y/3*3;
for(int i=sx;i<sx+3;i++)
for(int j=sy;j<sy+3;j++)
if(ans[i][j]==num) return 0;
return 1;
}
void print()
{
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
if(j==0) printf("%d",ans[i][j]);
else printf(" %d",ans[i][j]);
if(j==8) printf("\n");
}
}
void dfs(int k)
{
if(mark==1) return;
if(k==81){
mark=1;
print();
return;
}
int x=k/9;
int y=k%9;
if(mat[x][y]!=0) dfs(k+1);
else for(int i=1;i<=9;i++)
{
if(can1(k,i)&&can2(k,i)&&can3(k,i))
{
ans[x][y]=i;
dfs(k+1);
ans[x][y]=0;
}
}
}
int main()
{
bool first=1;
while(cin>>c)
{
if(c!='?') mat[0][0]=ans[0][0]=c-'0';
else mat[0][0]=ans[0][0]=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
if(i==0&&j==0) continue;
cin>>c;
if(c!='?') mat[i][j]=ans[i][j]=c-'0';
else mat[i][j]=ans[i][j]=0;
}
if(first){first=0;}
else printf("\n");
mark=0;
memset(flag,0,sizeof(flag));
dfs(0);
}
return 0;
}
优质内容筛选与推荐>>
1、spring mvc 常用前后台数据交互的注解
2、彻底弄明白之java多线程中的volatile
3、Could not load type 'Microsoft.TeamFoundation.workitemTracking.Client.WorkItemTypeDeniedOrNotExistException' from assemb
4、终于加入博客园了！！！
5、java运行环境增加字体