hiho一下 第135周 九宫 （枚举幻方）

描述

小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

题意

给出一个不完整的三阶幻方，问能否将它还原，如果可以还原成多种情况，输出 Too Many ，否则输出唯一还原后的幻方。

思路

怎么说呢！这道题，想了想这样的三阶幻方，中心的数字一定是5，并且四个角一定是偶数，不论怎么旋转变化，总共也不超过10种情况。

于是，很轻松的写出了八种所有情况。

接下来便是把输入的不完整幻方与所有的情况对比，若符合多个，便说明还原之后的幻方不唯一，否则输出可以还原到的幻方。

AC 代码

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
using namespace std;

int a[8][3][3]=     //三阶幻方旋转总共只有八种情况，可以很快写出来的
{
    {
        {8,1,6},
        {3,5,7},
        {4,9,2}
    },
    {
        {6,1,8},
        {7,5,3},
        {2,9,4}
    },
    {
        {4,9,2},
        {3,5,7},
        {8,1,6}
    },
    {
        {2,9,4},
        {7,5,3},
        {6,1,8}
    },
    {
        {6,7,2},
        {1,5,9},
        {8,3,4}
    },
    {
        {8,3,4},
        {1,5,9},
        {6,7,2}
    },
    {
        {2,7,6},
        {9,5,1},
        {4,3,8}
    },
    {
        {4,3,8},
        {9,5,1},
        {2,7,6}
    }
};

bool judge(int a[3][3],int s[3][3])
{
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            if(s[i][j]!=0&&a[i][j]!=s[i][j])
                return false;
    return true;
}

int main()
{
    int s[3][3],count=0,sk;
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            scanf("%d",&s[i][j]);
    for(int i=0; i<8; i++)
        if(judge(a[i],s))
        {
            sk=i;
            count++;
        }
    if(count==1)
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
                printf(j!=2?"%d ":"%d\n",a[sk][i][j]);
    else printf("Too Many\n");
    return 0;
}