一道九宫格的dfs,蒟蒻的程序一直输出1
题目在这里: 蒟蒻的程序:
#include<bits/stdc++.h>
using namespace std;
int a[11][11]={},vis1[11][11]={},vis2[11][11]={},vis3[11][11]={},ans=0,fi[11][11]={};//vis1记录这个列有没有,vis2记录这个行有没有 vis3记录这个九宫格有没有 fi记录一开始有没有
int dfs(int dep)
{
int p,q;
p=(dep-1)%9+1,q=(dep-p)/9+1;//p为列
int x=(q-1)/3+1,y=(p-1)/3+1;
int an=(x-1)*3+y;
if(fi[q][p]!=0) dfs(dep+1);
if(dep==81)
{
return (100*a[1][1]+10*a[1][2]+a[1][3]);
}
else
{
for(int i=1;i<=9;i++)
{
if((!vis1[p][i])&&(!vis2[q][i])&&(!vis3[an][i]))
{
a[q][p]=i;
vis1[p][i]=1;
vis2[q][i]=1;
vis3[an][i]=1;
dfs(dep+1);
a[q][p]=0;
vis1[p][i]=0;
vis2[q][i]=0;
vis3[an][i]=0;
}
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int k=1;k<=9;k++)
{
for(int j=1;j<=9;j++)
{
vis1[k][j]=0;
vis2[k][j]=0;
vis3[k][j]=0;
a[k][j]=0;
fi[k][j]=0;
}
}
for(int m=1;m<=9;m++)
{
for(int y=1;y<=9;y++)
{
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
a[m][y]=ch-'0';
if(a[m][y]!=0)
{
int p=(m-1)/3+1,q=(y-1)/3+1;
int an=(p-1)*3+q;
vis2[m][a[m][y]]=1;
vis1[y][a[m][y]]=1;
vis3[an][a[m][y]]=1;
fi[m][y]=1;
}
}
}
ans+=dfs(1);
}
printf("%d",ans);
}