A20914. 数独
2026-08-13 13:24:36
发布于：浙江
17阅读
0回复
0点赞
不是这代码 AC 掉了题目补充数据还 TLE 怎么优化啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！
#include <bits/stdc++.h>
using namespace std;
int a[10][10], f;
void dfs(int x, int y) {
if (x > 9) {
f = 1;
return ;
}
if (a[x][y] == 0) {
int h[10] = {0}, l[10] = {0}, g[10] = {0};
for (int i = 1; i <= 9; ++i)
if (a[x][i]) {
if (h[a[x][i]]) return ;
else h[a[x][i]] = 1;
}
for (int i = 1; i <= 9; ++i)
if (a[i][y]) {
if (l[a[i][y]]) return ;
else l[a[i][y]] = 1;
}
int gh = (x - 1) / 3 + 1, gl = (y - 1) / 3 + 1;
for (int i = gh * 3 - 2; i <= gh * 3; ++i)
for (int j = gl * 3 - 2; j <= gl * 3; ++j)
if (a[i][j]) {
if (g[a[i][j]]) return ;
else g[a[i][j]] = 1;
}
for (int i = 1; i <= 9; ++i)
if (!h[i] && !l[i] && !g[i]) {
a[x][y] = i;
dfs(x + y / 9, y % 9 + 1);
if (f) return ;
}
a[x][y] = 0;
} else {
dfs(x + y / 9, y % 9 + 1);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
cin >> a[i][j];
dfs(1, 1);
for (int i = 1; i <= 9; ++i) {
for (int j = 1; j <= 9; ++j)
cout << a[i][j] << " ";
cout << "\n";
}
}
全部评论 1
输入
9 0 0 8 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 3 0 1 0 0 0 0 0 6 0 0 0 0 4 0 0 0 7 0 7 0 8 6 0 0 0 0 0 0 0 0 0 3 0 1 0 0 4 0 0 0 0 0 2 0 0输出
9 7 2 8 5 3 6 1 4 1 4 6 2 7 9 5 3 8 5 8 3 1 4 6 7 2 9 6 2 4 7 1 8 9 5 3 8 1 7 3 9 5 4 6 2 3 5 9 4 6 2 8 7 1 7 9 8 6 2 1 3 4 5 2 6 5 9 3 4 1 8 7 4 3 1 5 8 7 2 9 62026-08-14 来自 浙江
0
有帮助，赞一个