求调一道站外题
  • 板块灌水区
  • 楼主Withers
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/4/20 18:53
  • 上次更新2023/11/5 00:18:57
查看原帖
求调一道站外题
481851
Withers楼主2021/4/20 18:53

一道九宫格的dfs,蒟蒻的程序一直输出1

题目在这里: 九宫格.PNG 蒟蒻的程序:

#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);
}
2021/4/20 18:53
加载中...