TLE80pts剪枝求调
  • 板块P1784 数独
  • 楼主cqbzrjx
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/8/17 09:07
  • 上次更新2024/8/17 11:26:08
查看原帖
TLE80pts剪枝求调
964148
cqbzrjx楼主2024/8/17 09:07
/*
LuoGu P1784 数独
*/
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
bool vis;
inline bool check(int x,int y,int pos)
{
	for(int i = 0;i < 9;i++)
	{
		if(a[i][y] == pos) return 0;
	}
	for(int i = 0;i < 9;i++)
	{
		if(a[x][i] == pos) return 0;
	}
	int fx = x / 3 * 3,fy = y / 3 * 3;
	for(int i = 0;i < 3;i++)
	{
		for(int j = 0;j < 3;j++)
		{
			if(a[i + fx][j + fy] == pos) return 0;
		}
	}
	return 1;
}
inline bool solve()
{
	if(vis) return;
	for(int i = 0;i < 9;i++)
	{
		for(int j = 0;j < 9;j++)
		{
			if(a[i][j] == 0)
			{
				for(int k = 1;k <= 9;k++)
				{
					if(check(i,j,k))
					{
						a[i][j] = k;
						if(solve()) return 1;
						else a[i][j] = 0;
					}
				}
				return 0;
			}
		}
	}
	return 1;
}
inline void print()
{
	for(int i = 0;i < 9;i++)
	{
		for(int j = 0;j < 9;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<"\n";
	}
}
inline void init()
{
	for(int i = 0;i < 9;i++)
	{
		for(int j = 0;j < 9;j++)
		{
			cin>>a[i][j];
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
	solve();
	print();
	return 0;
}
2024/8/17 09:07
加载中...