开平建设局网站,动画专业大学,响应式网站解决方案,深圳福永做网站题目描述 小明最近在教邻居家的小朋友小学奥数#xff0c;而最近正好讲述到了三阶幻方这个部分。 三阶幻方指的是将1~9不重复的填入一个33的矩阵当中#xff0c;使得每一行、每一列和每一条对角线的和都是相同的。 三阶幻方又被称作九宫格#xff0c;在小学奥数里有一句非常…题目描述 小明最近在教邻居家的小朋友小学奥数而最近正好讲述到了三阶幻方这个部分。 三阶幻方指的是将1~9不重复的填入一个33的矩阵当中使得每一行、每一列和每一条对角线的和都是相同的。 三阶幻方又被称作九宫格在小学奥数里有一句非常有名的口诀 “二四为肩六八为足左三右七戴九履一五居其中” 通过这样的一句口诀就能够非常完美的构造出一个九宫格来。 4 9 2 3 5 7 8 1 6 有意思的是所有的三阶幻方都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。 现在小明准备将一个三阶幻方不一定是上图中的那个中的一些数抹掉交给邻居家的小朋友来进行还原并且希望她能够判断出究竟是不是只有一个解。 而你呢也被小明交付了同样的任务但是不同的是你需要写一个程序~ 输入 输入一个33的矩阵其中为0的部分表示被小明抹去的部分。 对于100%的数据满足给出的矩阵至少能还原出一组可行的三阶幻方。 输出 如果仅能还原出一组可行的三阶幻方则将其输出否则输出“Too Many”不包含引号。 样例输入 0 7 2 0 5 0 0 3 0 样例输出 6 7 2 1 5 9 8 3 4
解题思路 用全排列函数枚举先判断是不是在题目所给的矩阵基础上填写的然后统计符合题意的次数。
知识点3阶幻方每一行、每一列和每一条对角线的和都是15其他阶次的幻方其每一行、每一列和每一条对角线的和也都是某个常数
代码如下
#include iostream
#include algorithmusing namespace std;int a[] {1, 2, 3, 4, 5, 6, 7, 8, 9};//用来枚举
int b[10];//符合情况的地图
int vis[10];//标记初始放置的数字的位置
int mp[10];//初始地图bool check() {for (int i 0; i 8; i) {if (vis[i] ! a[i] vis[i] ! 0)return false;}if (a[0] a[1] a[2] ! 15 )return false;if (a[3] a[4] a[5] ! 15)return false;if (a[6] a[7] a[8] ! 15)return false;if (a[0] a[3] a[6] ! 15)return false;if (a[1] a[4] a[7] ! 15)return false;if (a[2] a[5] a[8] ! 15)return false;if (a[0] a[4] a[8] ! 15)return false;if (a[2] a[4] a[6] ! 15)return false;for (int i 0; i 8; i)b[i] a[i];return true;
}int main() {for (int i 0; i 8; i) {cin mp[i];if (mp[i] ! 0)vis[i] mp[i];}int ans 0;do {if (check())ans;if (ans 1) {cout Too Many endl;return 0;}} while (next_permutation(a, a 9));int count 0;for (int i 0; i 8; i) {count;cout b[i] ;if (count % 3 0)cout endl;}return 0;}
