求助,全部MLE
  • 板块P1784 数独
  • 楼主ryanwyr
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/24 14:41
  • 上次更新2024/1/24 16:31:25
查看原帖
求助,全部MLE
1040524
ryanwyr楼主2024/1/24 14:41

为啥全MLE啊??????

#include<bits/stdc++.h>
using namespace std;
int a[10][10];
bitset<10> b1[10],b2[10],b3[10];
int gai(int x,int y,int k)
{
	b1[x][k]=0;
	b2[y][k]=0;
	b3[(x-1)/3*3+(y-1)/3+1][k]=0;
}
int _gai(int x,int y,int k)
{
	b1[x][k]=1;
	b2[y][k]=1;
	b3[(x-1)/3*3+(y-1)/3+1][k]=1;
}
int st()
{
	int ans=0;
	for(int i=1;i<=9;i++) b1[i]=b2[i]=b3[i]=1023;
	for(int i=1;i<=9;i++) for(int j=1;j<=9;j++)
	{
	    cin >> a[i][j];
	    if(a[i][j]>0)
		{
		    gai(i,j,a[i][j]);
		    ans++;
		}
	}
	return ans;
}
void out()
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++) cout << a[i][j] << ' ';
		cout << endl;
	}
	exit(0);
}
int g(bitset<10> x)
{
	int ans=0;
	for(int i=1;i<=9;i++) if(x[i]) ans++;
	return ans;
}
bitset<10> can(int x,int y)
{
	return b1[x]&b2[y]&b3[(x-1)/3*3+(y-1)/3+1];
}
void dfs(int s)
{
	if(s==81) out();
	int mi=10,mx,my;
	for(int i=1;i<=9;i++) for(int j=1;j<=9;j++)
	    if(a[i][j]==0 && g(can(i,j))<mi) mi=g(can(i,j)),mx=i,my=j;
	for(int i=1;i<=9;i++) if(can(mx,my)[i])
	{
		a[mx][my]=i;
		gai(mx,my,i);
		dfs(s+1);
		_gai(mx,my,i);
	}
	a[mx][my]=0;
}
int main()
{
	dfs(st());
	return 0;
}
2024/1/24 14:41
加载中...