終于A了
140ms+
說一下我的思路：
接受數(shù)據(jù)后，把每個為0的位置記錄下來(tatus[])，并計算該位置可能的狀態(tài)數(shù)，然后排序，從狀態(tài)數(shù)最小的開始搜索。也就是僅搜索為0的位置。
不過對于這組數(shù)據(jù)：
9
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
我估計我程序半年都出不了結(jié)果
check(x,y,p)函數(shù)檢查(x,y)位置是否可以放p這個值。
cal()函數(shù)計算初始可能的狀態(tài)數(shù)。
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int sudo[10][10];
struct type
{
int x,y,count;
}status[82];
int num_status=0;
bool check(int i, int j, int t)//judge if it is possible to put digit t at (i,j)
{
for(int k=1; k<=9; k++)
if(sudo[i][k]==t)return false;
for(int k=1; k<=9; k++)
if(sudo[k][j]==t)return false;
int x=(i-1)/3*3+1 ,y=(j-1)/3*3+1;
for(int s=0; s<=2; s++)
for(int tt=0; tt<=2; tt++)
if(sudo[x+s][y+tt]==t)return false;
return true;
}
int cal(int i, int j)//calculate the the number of possible status of (i,j)
{
int cnt=0;
for(int p=1; p<=9; p++)
if(check(i,j,p))cnt++;
return cnt;
}
bool cmp(const type &a, const type &b)
{
return a.count<b.count;
}
void dfs(int cnt,bool &find)
{
if(cnt>num_status)return ;
if(find){ return ;}
int x=status[cnt].x;
int y=status[cnt].y;
if(cnt==num_status)
{
for(int p=1; p<=9; p++)
if(check(x,y,p))
{
sudo[x][y]=p;
for(int i=1; i<=9; i++)
{
for(int j=1; j<=9; j++)
cout<<sudo[i][j];
cout<<endl;
}
find=true;
return ;
}
return ;
}
for(int p=1; p<=9; p++)
{
if(check(x,y,p))
{
sudo[x][y]=p;
dfs(cnt+1,find);
}
sudo[x][y]=0; //剛開始一直錯就因為沒置0，check函數(shù)當(dāng)當(dāng)前位置是0的時候才有效。
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(sudo,0,sizeof sudo);
char ch;
num_status=0;
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
{
cin>>ch;
sudo[i][j]=int(ch-'0');
}
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
if(sudo[i][j]==0)
{
num_status++;
status[num_status].x=i; status[num_status].y=j;
status[num_status].count=cal(i,j);
}
sort(status+1,status+1+num_status,cmp);
// for(int i=1; i<=num_status ;i++)
// cout<<' '<<status[i].x<<' '<<status[i].y<<' '<<status[i].count<<endl;
bool find=false;
dfs(1,find);
if(num_status==0)
{
for(int i=1; i<=9; i++)
{
for(int j=1; j<=9; j++)
cout<<sudo[i][j];
cout<<endl;
}
}
}
system("pause");
return 0;
}