[蓝桥 2017]九宫幻方

九宫幻方

题目描述

小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将 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 i=1;i<=3;i++)for(int j=1;j<=3;j++)cin>>a[i][j];//读入样例矩阵for(int i=1;i<=9;i++)p[i]=i;int cnt=0;//统计九宫幻方的个数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 i=1;i<=3;i++){for(int j=1;j<=3;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 i=1;i<=3;i++){int tmp1 = 0,tmp2 = 0;//tmp1表示行和，temp2表示列和for(int j=1;j<=3;j++){tmp1+=b[i][j];tmp2+=b[j][i];}if(tmp1 !=sum ||tmp2 !=sum)ok =false;//如果行的和或列的和不等于sum，则排列矩阵不是九宫幻方}if(!ok) continue;//如果不是九宫幻方，就跳过cnt++;//九宫幻方的个数＋1if(cnt>=2)return cout<<"Too Many\n",0;//九宫幻方的个数》=2，直接输出Too Many，结束程序for(int i = 1;i<=3;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 i=1;i<=3;i++){for(int j=1;j<=3;j++){if(j==1)cout<<ans[i][j];elsecout<<" "<<ans[i][j];}cout<<endl;}// 请在此输入您的代码return 0;
}