比赛 |
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
}