60分 TLE2个点
查看原帖
60分 TLE2个点
781438
threebody_santi楼主2024/11/23 12:22
#include<bits/stdc++.h>
using namespace std;
int a[20][20];
int ov=0;
int vis[20][20];
int h[10][10],l[20][20],k[20][20];
pair<int,int> p[100];
int cnt=0;
int get_block(int x,int y)
{
	if(x<=3 && y<=3)
	{
		return 1;
	}
	if(x<=3 && y<=6)
	{
		return 2;
	}
	if(x<=3 && y<=9)
	{
		return 3;
	}
	if(x<=6 && y<=3)
	{
		return 4;
	}
	if(x<=6 && y<=6)
	{
		return 5;
	}
	if(x<=6 && y<=9)
	{
		return 6;
	}
	if(x<=9 && y<=3)
	{
		return 7;
	}
	if(x<=9 && y<=6)
	{
		return 8;
	}
	if(x<=9 && y<=9)
	{
		return 9;
	}
}
int check(int x,int y,int num)
{
	int t=get_block(x,y);
	if(h[x][num]==1 || l[y][num]==1 || k[t][num]==1)
	{
		return 0;
	}
	return 1;
}
void dfs(int s)
{
	int x=p[s].first;
	int y=p[s].second;
	//cout<<x<<" "<<y<<endl;
	if(s>cnt)
	{
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
		exit(0);
	}
	for(int i=1;i<=9;i++)
	{
		int t=get_block(x,y);
		if(check(x,y,i)==1)
		{
			//cout<<1<<endl; 
			a[x][y]=i;
			h[x][i]=1;
			l[y][i]=1;
			k[t][i]=1;
			dfs(s+1);
			a[x][y]=0;
			h[x][i]=0;
			l[y][i]=0;
			k[t][i]=0;
		}
	}
}
int main()
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]==0)
			{
				p[++cnt].first=i;
				p[cnt].second=j;
			}
			int x=a[i][j];
			if(a[i][j]!=0)
			{
				int t=get_block(i,j);
				h[i][x]=1;
				l[j][x]=1;
				k[t][x]=1;
			}
		}
	}
	dfs(1);
	return 0;
}

60分,t2个点

2024/11/23 12:22
加载中...