当前位置：首页 > 题解与讨论 > 正文内容

ACFun-contest1154-6

shudaojikas2个月前 (07-10)题解与讨论863

T6
题目
题目描述
数独是根据 
9
×
9
9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 
1
−
9
1−9 ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入格式
一个未填的数独。

输出格式
填好的数独。

样例
样例输入
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0
样例输出
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
数据范围

题解:
dfs一个，结束

这是答案:
T6
#include <bits/stdc++.h>
using namespace std;
int a[10][10], h[10][10], l[10][10], k[10][10];
int fun(int x, int y){
	return (x - 1) / 3 * 3 + (y - 1)/ 3 + 1;
}void dfs(int x, int y){
	int tx = x, ty = y;
	if (ty > 1){
		ty--;
	}else{
		tx--;
		ty = 9;
	}if (x == 0 && y == 9){
		for (int i = 1;i < 10;i++){
			for (int j = 1;j < 10;j++){
				cout << a[i][j] <<' ';
			}cout << endl;
		}return;
	}else{
		if (a[x][y]){
			dfs (tx, ty);
		}else{
			for (int i = 9;i > 0;i--){
				if (!h[x][i] && !l[y][i] && !k[fun(x, y)][i]){
					a[x][y] = i;
					h[x][i] = 1;
					l[y][i] = 1;
					k[fun(x, y)][i] = 1;
					dfs(tx, ty);
					a[x][y] = 0;
					h[x][i] = 0;
					l[y][i] = 0;
					k[fun(x, y)][i] = 0;
				}
			}
		}
	}
}int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for (int i = 1;i < 10;i++){
		for (int j = 1;j < 10;j++){
			cin >> a[i][j];
			if (a[i][j]){
				h[i][a[i][j]] = 1;
				l[j][a[i][j]] = 1;
				k[fun(i, j)][a[i][j]] = 1;
			}
		}
	}dfs (9, 9);
	return 0;
}

返回列表

上一篇：【站务】网站更新日志

下一篇：妈祖保佑！