80分,一个超时,求调
  • 板块P1784 数独
  • 楼主pgm_520
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/10 23:37
  • 上次更新2024/7/11 09:34:22
查看原帖
80分,一个超时,求调
1243041
pgm_520楼主2024/7/10 23:37
#include<iostream>
using namespace std;
int a[15][15],sum=0,px[90],py[90],hang[10][10],lie[10][10],gong[4][4][10];
void pt()
{
	int i,j; 
	for(i=1;i<=9;i++)
	{
		for(j=1;j<=9;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
}
void sd(int step)
{
	int i;  
	if(step==sum+1)
	{
		pt();
		return ;
	}      
	for(i=1;i<=9;i++)
	{
		if( hang[px[step]][i] ==0 && lie[py[step]][i] ==0 && gong[(px[step]+2)/3] [(py[step]+2)/3] [i]==0 )
		{
			a[px[step]][py[step]]=i;
			hang[px[step]][i]=1;
			lie[py[step]][i]=1;
			gong[(px[step]+2)/3][(py[step]+2)/3][i]=1;
			sd(step+1);
			a[px[step]][py[step]]=0;
			hang[px[step]][i]=0;
			lie[py[step]][i]=0;
			gong[(px[step]+2)/3][(py[step]+2)/3][i]=0;
		}
	}
	
}
int main()
{
	int i,j;
	for(i=1;i<=9;i++)
	{
		for(j=1;j<=9;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==0)
			{
				sum++;
				px[sum]=i;
				py[sum]=j;
			}
			else
			{
				hang[i][a[i][j]]=1;
				lie[j][a[i][j]]=1;
				gong[(i+2)/3][(j+2)/3][a[i][j]]=1;
			}
		}
	}
	sd(1);
	return 0;
}
2024/7/10 23:37
加载中...