80分求调
  • 板块P1784 数独
  • 楼主youyew2007
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/1 09:50
  • 上次更新2023/10/27 09:23:58
查看原帖
80分求调
349545
youyew2007楼主2022/10/1 09:50

80分,第四个点TLE,求大佬帮忙看看蒟蒻的问题

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 25

int a[N][N],v1[N][N],v2[N][N],v3[N][N];
int id[10][10] = { {},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9} };

inline void dfs(register int x,register int y)
{
	if(x > 9)
	{
		for(register int i = 1;i <= 9;i++)
		{
			for(register int j = 1;j <= 9;j++)
			{
				cout << a[i][j] << ' ';
			}
			cout << endl;
		}
		return;
	}
	if(a[x][y] != 0)
	{
		if(y == 9)
			dfs(x + 1,1);
		else
			dfs(x,y + 1);
		return;
	}
	for(register int i = 1;i <= 9;i++)
	{
		if(!v1[x][i] && !v2[y][i] && !v3[id[x][y]][i])
		{
			a[x][y] = i;
			v1[x][i] = v2[y][i] = v3[id[x][y]][i] = 1;
			if(y == 9)
				dfs(x + 1,1);
			else
				dfs(x,y + 1);
			a[x][y] = 0;
			v1[x][i] = v2[y][i] = v3[id[x][y]][i] = 0;
		}
	}
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	for(register int i = 1;i <= 9;i++)
	{
		for(register int j = 1;j <= 9;j++)
		{
			cin >> a[i][j];
			if(a[i][j])
			{
				v1[i][a[i][j]] = 1;
				v2[j][a[i][j]] = 1;
				v3[id[i][j]][a[i][j]] = 1;
			}
		}
	}
	dfs(1,1);
	return 0;
}
2022/10/1 09:50
加载中...