比赛 20250409练习赛 评测结果 AAAAAAAAATATAATTAAAA
题目名称 靶形数独 最终得分 80
用户昵称 喵喵喵 运行时间 10.083 s
代码语言 C++ 内存使用 3.31 MiB
提交时间 2025-04-09 20:12:38
显示代码纯文本
#include <bits/stdc++.h>
#define herta return 0;
using namespace std;
int n;
struct Node
{
	int x,y;
}a[1000];
int g[20][20],m = 0;
long long ans = 0;
bool row[20][20],col[20][20],grid[5][5][20];
int score[20][20] = {
	{6,6,6,6,6,6,6,6,6},
	{6,7,7,7,7,7,7,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9,9,8,7,6},
	{6,7,8,8,8,8,8,7,6},
	{6,7,7,7,7,7,7,7,6},
	{6,6,6,6,6,6,6,6,6},
};
bool dfs(int k,int temp)
{
	if(k == m + 1)
	{
		if(temp <= ans) return false;
		else
		{
			ans = temp;
		}
	}
	int x = a[k].x,y = a[k].y;
	for(int num = 1;num <= 9;num++)
	{
		if(row[x][num] || col[y][num] || grid[x/3][y/3][num]) continue;
		g[x][y] = num;
		row[x][num] = col[y][num] = grid[x/3][y/3][num] = 1;
		temp += score[x][y] * num;
		if(dfs(k+1,temp)) return true;
		g[x][y] = 0;
		row[x][num] = col[y][num] = grid[x/3][y/3][num] = 0;
		temp -= score[x][y] * num;
	}
	return false;
}
int main()
{
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	memset(row,0,sizeof(row));
	memset(col,0,sizeof(col));
	memset(a,0,sizeof(a));
	memset(g,0,sizeof(g));
	memset(grid,0,sizeof(grid));
	m = 0;
	for(int j = 0;j < 9;j++)
	{
		for(int k = 0;k < 9;k++)
		{
			int op;
			cin >> op;
			g[j][k] = op;
			if(op == 0)
			{
				a[++m] = {j,k};
			}
			ans += score[j][k] * op;
			row[j][op] = col[k][op] = grid[j/3][k/3][op] = 1;
		}
	}
	int flag = ans;
	dfs(1,ans);
	if(ans != flag)
	{
		cout << ans << endl;
		herta
	}
	else cout << -1 << endl;
	herta
}