1.题目要求判断给出一个幻方，只有一种解法则输出解放，否则输出Too Many；
2.采用深度搜索即可，并且每行，每列，每条对角线的和为15，如果填充后任意一个和不等于15，直接进行剪枝。
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。
三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。
有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小Hi准备将一个三阶幻方（不一定是上图中的那个）中的一些数组抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一组解。
而你呢，也被小Hi交付了同样的任务，但是不同的是，你需要写一个程序~
输入
输入仅包含单组测试数据。
每组测试数据为一个3*3的矩阵，其中为0的部分表示被小Hi抹去的部分。
对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。
输出
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。
- 样例输入
-
0 7 2 0 5 0 0 3 0
- 样例输出
-
6 7 2 1 5 9 8 3 4
AC代码：
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<bitset>
//#include "siukwanAlloctor.h"
using namespace std;
bool check(vector<vector<int>>&a)
{
vector<int> row(3, 0);
vector<int> col(3, 0);
vector<int> angle(2, 0);
//计算行总和
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
if (a[i][j] == 0)
{
row[i] = 0;
break;
}
else
row[i] += a[i][j];
}
if (row[i] != 0 && row[i] != 15) return false;
}
//计算列总和
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
if (a[j][i] == 0)
{
col[i] = 0;
break;
}
else
col[i] += a[j][i];
}
if (col[i] != 0 && col[i] != 15) return false;
}
//计算对角线
if (a[0][0] != 0 && a[1][1] != 0 && a[2][2] != 0)
angle[0] = a[0][0] + a[1][1] + a[2][2];
if (angle[0] != 0 && angle[0] != 15) return false;
if (a[2][0] != 0 && a[1][1] != 0 && a[0][2] != 0)
angle[1] = a[2][0] + a[1][1] + a[0][2];
if (angle[1] != 0 && angle[1] != 15) return false;
return true;
}
void dfs(vector<vector<int>>&a, int need, vector<bool>&used,vector<vector<vector<int>>>&result)
{
if (result.size() >= 2) return;
if (need == 0)
{
if (result.size()==0)
result.push_back(a);
else
{
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
if (result[0][i][j] != a[i][j])
{
result.push_back(a);
return;
}
}
}
return;
}
}
for (int k = 1; k < used.size(); ++k)
{
if (!used[k])
{
used[k] = true;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
if (a[i][j] == 0)//需要填充
{
a[i][j] = k;//填充为k
if (check(a))//检测矩阵
dfs(a, need - 1, used, result);
a[i][j] = 0;//填充为k
}
}
}
used[k] = false;
}
}
}
int main()
{
int need = 0;
vector<vector<int>> a(3, vector<int>(3, 0));
vector<bool> used(10,false);
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
scanf("%d", &a[i][j]);
if (a[i][j] == 0) need++;
used[a[i][j]] = true;
}
}
vector<vector<vector<int>>> result;
dfs(a, need, used, result);
if (result.size()>1)
cout << "Too Many" << endl;
else
{
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
cout << result[0][i][j];
if (j != 2)
cout << " ";
else
cout << endl;
}
}
}
return 0;
}