建站套餐和定制网站的区别,临汾外贸网站建设价格,织梦做中英文网站详细步骤,网页版快手题目
九宫幻方https://www.lanqiao.cn/problems/100/learning/?page1first_category_id1name%E4%B9%9D 思路和解题方法 一 #xff08;DFS) 首先#xff0c;定义了一些全局变量和数组。vis数组用于标记已经出现过的数字#xff0c;a数组用于存储数独的初始状态…题目
九宫幻方https://www.lanqiao.cn/problems/100/learning/?page1first_category_id1name%E4%B9%9D 思路和解题方法 一 DFS) 首先定义了一些全局变量和数组。vis数组用于标记已经出现过的数字a数组用于存储数独的初始状态和中间状态ans数组用于存储找到的解决方案p数组用于存储空白格子的坐标n表示空白格子的数量cnt记录解决方案的数量。 check()函数用于检查当前填充的数字是否满足数独的规则。它首先计算对角线上的元素之和然后检查每行和每列的和是否相等并返回一个布尔值表示结果。 dfs()函数是核心部分使用递归实现深度优先搜索。它从第一个空白格子开始填充数字每次填充一个数字后递归调用自身继续填充下一个空白格子直到所有空白格子都填充完毕。如果找到了符合数独规则的解决方案则将其记录在ans数组中并增加cnt的计数。 在main()函数中首先读入数独的初始状态并初始化相关变量。然后调用dfs()函数进行搜索。最后根据搜索结果输出解决方案或提示Too Many表示找到了多个解决方案。 需要注意的是该程序假设输入的数独有唯一解或没有解。如果存在多个解则只会输出其中一个解。如果不存在解则输出Too Many表示无法确定唯一解。 c 代码 1
#includebits/stdc.h
using namespace std;int vis[10],a[5][5],ans[5][5];
// vis数组用来标记数字是否使用过a数组记录数独题目的矩阵ans数组用来存储解决方案
int n1,cnt;
pairint ,intp[10];
// p数组用来存储空白格的坐标n记录空白格的个数
bool check(){int suma[1][1]a[2][2]a[3][3];// 先计算左上到右下的斜线上的数字之和if(sum!a[1][3]a[2][2]a[3][1]) return false;// 再计算右上到左下的斜线上的数字之和如果不相等则不是数独的解for(int i1;i3;i){int tmp10,tmp20;for(int j1;j3;j)tmp1a[i][j],tmp2a[j][i];//行和列的和相等 if(tmp1!sum||tmp2!sum) return false;}// 分别计算每行每列的数字之和如果与斜线上的数字之和不相等则不是数独的解return true;
} void dfs(int now){if(nown){if(check()){cnt;for(int i1;i3;i)for(int j1;j3;j)ans[i][j]a[i][j];// 如果当前数独矩阵是解则令ans数组等于当前矩阵}return;}int xp[now].first,yp[now].second;for(int k1;k9;k){if(vis[k])continue;a[x][y]k;vis[k]1;dfs(now1);a[x][y]0;vis[k]0;// 搜索之前先标记数字已经使用过搜索完之后再回溯}
}int main()
{for(int i1;i3;i)for(int j1;j3;j){cina[i][j];if(!a[i][j])p[n]make_pair(i,j);// 记录空白格的坐标vis[a[i][j]]1; // 标记数字已经使用过}dfs(1);//从第一个空白格开始搜索if(cnt1){for(int i1;i3;i)for(int j1;j3;j)coutans[i][j] \n[j3];}else coutToo Many\n;// 如果有多个解则输出Too Manyreturn 0;}思路和解题方法 二 全排列 从标准输入中读入一个包含9个整数的数组a。使用next_permutation函数生成arr数组的全排列并逐个判断是否满足数独的条件。如果某个排列满足数独条件并且与输入数组a匹配则将该排列赋值给数组a并增加计数器ans的值。最后根据计数器ans的值输出结果。如果有且仅有一个解则输出解如果有多个解则输出Too Many。 c 代码
#includeiostream
#includealgorithm
#includebits/stdc.h //包含一些常用的头文件例如vector、string等
using namespace std;int a[10]; //定义一个长度为10的数组a用于存储输入的数独初始状态
int ans 0; //计数器用于存储符合数独条件的解的个数
int arr[10] {1,2,3,4,5,6,7,8,9}; //定义一个长度为10的数组arr用于生成全排列//检查当前排列是否符合数独条件
bool check(int a[])
{int a1a[0]a[1]a[2];int a2a[3]a[4]a[5];int a3a[6]a[7]a[8];int a4a[0]a[3]a[6];int a5a[1]a[4]a[7];int a6a[2]a[5]a[8];int a7a[2]a[4]a[6];int a8a[0]a[4]a[8];if(a1a2a2a3a3a4a4a5a5a6a6a7a7a8) //如果8个和相等则返回true{return true;}return false; //否则返回false
}int main()
{for(int i 0;i9;i) //读入初始数独状态{cina[i];}while(next_permutation(arr,arr9)){ //生成arr数组的全排列逐个检查是否符合数独条件if(check(arr)) //如果符合数独条件{bool y true;for(int i 0;i9;i){if(a[i]!0a[i]!arr[i]) //如果输入的数独状态不为0且与当前排列不一致则说明不是想要的解{y false; //设置标志y为false}}if(y) //如果当前排列与输入的数独状态匹配{for(int i 0;i9;i) //将当前排列赋值给数组a{a[i] arr[i];}ans; //计数器ans加1}}}if(ans 1) //如果只有一个解则输出该解{int cnt 0; //计数器cnt用于输出格式控制for(int i 0;i9;i){if(cnt3){coutendl; //每输出三个数字换行cnt 0;}couta[i] ; //输出数独解cnt; //计数器加1}}else { //如果有多个解则输出Too Manyprintf(Too Many);}return 0;
}知识点解释
next_permutation() 全排列 next_permutation()是一个函数通常在编程语言中用于生成给定序列的下一个排列。它可以按照字典序升序生成给定序列的下一个排列并将其更新为下一个排列。 具体而言next_permutation()函数接受一个序列作为参数并将该序列重排为下一个字典序更大的排列。如果没有下一个更大的排列则将序列重排为最小的升序排列。该函数返回一个布尔值指示是否成功生成了下一个排列。 下面是一个示例展示了如何使用next_permutation()函数来生成给定序列的所有排列 #include iostream#include algorithmusing namespace std;int main() {int arr[] {1, 2, 3};// 生成并打印所有排列do {for (int i 0; i 3; i) {cout arr[i] ;}cout endl;} while (next_permutation(arr, arr 3));return 0;}
输出结果将是 1 2 31 3 22 1 32 3 13 1 23 2 1 这个例子展示了如何使用next_permutation()函数生成给定序列的所有排列并将它们打印出来。每次调用next_permutation()函数时原始数组会被修改为下一个排列直到没有更多的排列可生成为止。 需要注意的是next_permutation()函数在不同的编程语言和库中可能有略微不同的实现方式但其基本功能是相似的生成给定序列的下一个排列。 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
