山东网站建设优化,网站建设制作模板网站怎么做,关键词优化招商,朝阳区的互联网公司九宫幻方
题目描述
小明最近在教邻居家的小朋友小学奥数#xff0c;而最近正好讲述到了三阶幻方这个部分#xff0c;三阶幻方指的是将 1~9 不重复的填入一个 3*3 的矩阵当中#xff0c;使得每一行、每一列和每一条对角线的和都是相同的。
三阶幻方又被称作九宫格#xf…九宫幻方
题目描述
小明最近在教邻居家的小朋友小学奥数而最近正好讲述到了三阶幻方这个部分三阶幻方指的是将 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运行限制
最大运行时间1s最大运行内存: 256M
总通过次数: 1096 | 总提交次数: 1260 | 通过率: 87%
难度: 困难 标签: 2017, 暴力, 省赛, 搜索
代码分享
#include iostream
#include bits/stdc.h
using namespace std;
int p[10],a[5][5],b[5][5],ans[5][5];
int main()
{for(int i1;i3;i)for(int j1;j3;j)cina[i][j];//读入样例矩阵for(int i1;i9;i)p[i]i;int cnt0;//统计九宫幻方的个数do{b[1][1]p[1],b[1][2]p[2],b[1][3]p[3];b[2][1]p[4],b[2][2]p[5],b[2][3]p[6];b[3][1]p[7],b[3][2]p[8],b[3][3]p[9];//判断排列矩阵和样例矩阵是否匹配bool flag true;//flag ture表示匹配flag false表示不匹配for(int i1;i3;i){for(int j1;j3;j){if(!a[i][j]) continue;//只看非零部分if(a[i][j] ! b[i][j]) flag false;}}if(!flag) continue;//如果不匹配//判断排列矩阵是否是九宫幻方bool ok true;//ok ture表示排列矩阵是九宫幻方ok flase表示排列矩阵不是九宫幻方int sum b[1][1] b[2][2] b[3][3];//取一条对角线if(sum !b[1][3]b[2][2]b[3][1]) continue;//判断另一条对角线的和是否等于sum不等于就跳过for(int i1;i3;i){int tmp1 0,tmp2 0;//tmp1表示行和temp2表示列和for(int j1;j3;j){tmp1b[i][j];tmp2b[j][i];}if(tmp1 !sum ||tmp2 !sum)ok false;//如果行的和或列的和不等于sum则排列矩阵不是九宫幻方}if(!ok) continue;//如果不是九宫幻方就跳过cnt;//九宫幻方的个数1if(cnt2)return coutToo Many\n,0;//九宫幻方的个数》2直接输出Too Many结束程序for(int i 1;i3;i)for(int j 1;j 3;j)ans[i][j] b[i][j];//用ans记录下该九宫幻方}while(next_permutation(p 1,p 1 9));for(int i1;i3;i){for(int j1;j3;j){if(j1)coutans[i][j];elsecout ans[i][j];}coutendl;}// 请在此输入您的代码return 0;
}
