网络公司网站模版,设计公司企业标语,WordPress主题应用首页500,购物网站建设方案小明最近在教邻居家的小朋友小学奥数#xff0c;而最近正好讲述到了三阶幻方这个部分#xff0c;三阶幻方指的是将 1∼9 不重复的填入一个 33 的矩阵当中#xff0c;使得每一行、每一列和每一条对角线的和都是相同的。 三阶幻方又被称作九宫格#xff0c;在小学奥数里有一句… 小明最近在教邻居家的小朋友小学奥数而最近正好讲述到了三阶幻方这个部分三阶幻方指的是将 1∼9 不重复的填入一个 3×3 的矩阵当中使得每一行、每一列和每一条对角线的和都是相同的。 三阶幻方又被称作九宫格在小学奥数里有一句非常有名的口诀“二四为肩六八为足左三右七戴九履一五居其中”通过这样的一句口诀就能够非常完美的构造出一个九宫格来。 4 9 2 3 5 7 8 1 6 有意思的是所有的三阶幻方都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。 现在小明准备将一个三阶幻方不一定是上图中的那个中的一些数抹掉交给邻居家的小朋友来进行还原并且希望她能够判断出究竟是不是只有一个解。 而你呢也被小明交付了同样的任务但是不同的是你需要写一个程序~ 输入格式: 一个 3×3 的矩阵其中为 0 的部分表示被小明抹去的部分。数据保证给出的矩阵至少能还原出一组可行的三阶幻方。 输出格式: 如果仅能还原出一组可行的三阶幻方则将其输出否则输出 Too Many。 输入样例 0 7 2 0 5 0 0 3 0 输出样例 6 7 2 1 5 9 8 3 4 我的思路其实看到这道题还是觉得该用爆搜题目说每一种三阶幻方都由下边这个原始幻方旋转或镜像操作得来那我就直接爆搜一种幻方有镜像和旋转两种操作将已知的可行的幻方镜像后判断是否满足满足则ans1然后又将幻方旋转得到另一个幻方继续判断旋转四次会变为原来的幻方就重复了这就是结束条件注意一个幻方镜像生成的新幻方不需要再旋转生成新幻方B因为后边会有幻方通过镜像和旋转生成幻方B如果将镜像旋转就会有数据重复 4 9 2 3 5 7 8 1 6 代码 #includebits/stdc.h
using namespace std;
int a[3][3]{{4,9,2},{3,5,7},{8,1,6}};
int target[3][3];
int ans0;
int b[3][3];
bool check(int a[][3]){for(int i0;i3;i){for(int j0;j3;j){if(target[i][j]!0target[i][j]!a[i][j]){return false;}}}return true;
}
void counter(int a[][3]){if(check(a)){ans1;if(ans1){for(int i0;i3;i){for(int j0;j3;j)b[i][j]a[i][j];}}}
}
void dfs(int a[][3],int count){if(count4)return;counter(a);//镜像int temp[3][3]; for(int i0;i3;i){for(int j0;j3;j)temp[i][j]a[i][2-j];}counter(temp);//旋转 for(int i0;i3;i){for(int j0;j3;j){temp[i][j]a[2-j][i];}}dfs(temp,count1);
}
int main(){for(int i0;i3;i)for(int j0;j3;j)cintarget[i][j];dfs(a,0);if(ans1){for(int i0;i3;i){for(int j0;j3;j)coutb[i][j] ;coutendl;}}else coutToo Many;
}
不过我看了别人的题解他直接将幻方的所有可能写了出来然后直接一一判断是否与输入相符即可因为可能的幻方好像也就八个很容易列出来这算是我没想到的点了
