http://acm.pku.edu.cn/JudgeOnline/problem?id=2676
數(shù)獨(dú)
T了幾次終于過(guò)了!!代碼寫得很..純回溯的。剛開(kāi)始是正向搜，一直T，看了discuss反向搜就過(guò)了！估計(jì)是數(shù)據(jù)問(wèn)題。
Source Code
| Problem: 2676 |
|
User: lovecanon |
| Memory: 224K |
|
Time: 79MS |
| Language: C |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int map[11][11];
int PlaceIndex[11][11];
int NumOfPlace[11];
int check(int row,int col,int num)
{
int i,j;
for(i=((int )ceil(1.0*row/3)-1)*3+1;i<=((int )ceil(1.0*row/3))*3;i++)
for(j=((int )ceil(1.0*col/3)-1)*3+1;j<=((int )ceil(1.0*col/3))*3;j++)
{
if(map[i][j]==num) return 0;
}
for(i=1;i<=9;i++)
{
if(map[row][i]==num) return 0;
if(map[i][col]==num) return 0;
}
return 1;
}
int solve(int row,int t)
{
int i;
if(row<1) return 1;
if(t>NumOfPlace[row]) if(solve(row-1,1)) return 1;
for(i=1;i<=9;i++)
{
if(check(row,PlaceIndex[row][t],i))
{
map[row][PlaceIndex[row][t]]=i;
if(solve(row,t+1)) return 1;
map[row][PlaceIndex[row][t]]=0;
}
}
return 0;
}
int main()
{
int cases;
scanf("%d",&cases);getchar();
while(cases--)
{
int i,j;
memset(NumOfPlace,0,sizeof(NumOfPlace));
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
{
map[i][j]=getchar()-'0';
if(map[i][j]==0)
{
++NumOfPlace[i];
PlaceIndex[i][NumOfPlace[i]]=j;
}
}
getchar();
}
solve(9,1);
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
printf("%d",map[i][j]);
printf("\n");
}
}
return 0;
}