站长平台怎么做网站,网页设计与制作工资多少,常用的网站开发设计语言,网站分析怎么做166. 数独 - AcWing题库
数独 是一种传统益智游戏#xff0c;你需要把一个99 的数独补充完整#xff0c;使得数独中每行、每列、每个 33 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行#xff0…166. 数独 - AcWing题库
数独 是一种传统益智游戏你需要把一个9×9 的数独补充完整使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行包含 81 个字符代表数独的 81 个格内数据顺序总体由上到下同行由左到右。
每个字符都是一个数字1−9或一个 .表示尚未填充。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行表示输入结束。
输出格式
每个测试用例输出一行数据代表填充完全后的数独。
输入样例
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end输出样例
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936难度中等时/空限制1s / 64MB总通过数12606总尝试数22720来源《算法竞赛进阶指南》, POJ3074 , kuangbin专题算法标签
解析
DFS之剪枝与优化主要方法:
1.优化搜索顺序大部分情况下我们应该优先搜索分支较少的节点 2.排除等效冗余 3.可行性剪枝 4.最优性剪枝 5.记忆化搜索dp) 1.优化搜索顺序
先搜索可选状态少的。可以使用 row[i] (i:0~8)表示第0行到第8行所用过的数字1表示当前位置对应的数字没有使用过可以使用0表示当前位置对应的数字没有使用过不可以使用。
同样的 col[i] 记录列的状态cel[i] 记录九宫格的状态
2. 可行性剪枝
同样的通过上述数组判断某个数字在某个位置是否可行
同时此题对时间的要求很高所以我们还要使用 lowbit 函数提高判断速度使用 one 和 mp 数组记录某个数 1 的个数和表示 lowbit 函数返回的数字表示 1~9 中的哪个数 #includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
using namespace std;
typedef long long LL;
const int N 1 9;
string s;
int row[10], loc[10], cel[3][3];
int mp[N], one[N];void init() {for (int i 0; i 9; i) {row[i] (1 9) - 1;loc[i] (1 9) - 1;}for (int i 0; i 3; i) {for (int j 0; j 3; j) {cel[i][j] (1 9) - 1;}}
}int lowbit(int x) {return x -x;
}void change(int a, int b, int num, int flg) {if (flg) {row[a] - 1 num;loc[b] - 1 num;cel[a / 3][b / 3] - 1 num;s[a * 9 b] num 1;}else {cel[a / 3][b / 3] 1 num;row[a] 1 num;loc[b] 1 num;s[a * 9 b] .;}
}int dfs(int cnt) {if (cnt 0) {cout s endl;return 1;}int mn 10;int a0, b0;for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (s[i * 9 j] .) {int x row[i] loc[j] cel[i / 3][j / 3];if (one[x] mn) {mn one[x];a i;b j;}}}}int x row[a] loc[b] cel[a / 3][b / 3];while (x) {change(a, b, mp[lowbit(x)], 1);if (dfs(cnt - 1))return 1;change(a, b, mp[lowbit(x)], 0);x - lowbit(x); }return 0;
}int main() {//预处理one和mp数组for (int i 0; i 9; i) {mp[1 i] i;}for (int i 0; i 1 9; i)for (int j 0; j 9; j)one[i] i j 1;while (cin s) {if (s end)break;int cnt 0;init();for (int i 0,a0,b0; i 9; i) {for (int j 0,pos0; j 9; j) {pos i * 9 j;if (s[pos] .) {cnt;}else {row[i] - 1 (s[pos] - 1);loc[j] - 1 (s[pos] - 1);cel[i/3][j/3]- 1 (s[pos] - 1);}}}dfs(cnt);}return 0;
}
