历届试题九宫幻方-白红宇

历届试题九宫幻方

阅读量：4313 次

发布时间：2019-06-06

本文共 2474 字，大约阅读时间需要 8 分钟。

问题描述

　　小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

　　三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

　　4 9 2

　　3 5 7

　　8 1 6

　　有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。

　　而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~

输入格式

　　输入仅包含单组测试数据。

　　每组测试数据为一个3*3的矩阵，其中为0的部分表示被小明抹去的部分。

　　对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

输出格式

　　如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。

样例输入

0 7 2

0 5 0

0 3 0

样例输出

6 7 2

1 5 9

8 3 4

题目分析

　　推理可知，三阶幻方数量可控，因此可以先写一个dfs函数，把所有的三阶幻方的存储起来，再进行比对。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                using namespace std;int m[][3][3] = { { { 4,9,2},{ 3,5,7},{ 8,1,6}}, { { 6,7,2},{ 1,5,9},{ 8,3,4}}, { { 2,7,6},{ 9,5,1},{ 4,3,8}}, { { 4,3,8},{ 9,5,1},{ 2,7,6}}, { { 6,1,8},{ 7,5,3},{ 2,9,4}}, { { 2,9,4},{ 7,5,3},{ 6,1,8}}, { { 8,1,6},{ 3,5,7},{ 4,9,2}}, { { 8,3,4},{ 1,5,9},{ 6,7,2}},};int maze[3][3];int vist[10];int sum = 0;int index;int iscorrect() { for (int i = 0; i < 3; i++) { if (maze[i][0] + maze[i][1] + maze[i][2] != 15) return 0; if (maze[0][i] + maze[1][i] + maze[2][i] != 15) return 0; } if (maze[0][0] + maze[1][1] + maze[2][2] != 15) return 0; if (maze[0][2] + maze[1][1] + maze[2][0] != 15) return 0; return 1;}void print1(int ii) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { printf("%d ", m[ii][i][j]); } cout << endl; }}void print() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { printf("%d ", maze[i][j]); } cout << endl; } cout << endl;}void dfs(int index) { if (index == 9) { int flag = iscorrect(); if(flag == 1) print(); } for (int j = 1; j <= 9; j++) { if (vist[j] == 0) { maze[index / 3][index % 3] = j; //cout << index / 3 << " " << index % 3 << " " << j << endl; vist[j] = 1; dfs(index + 1); vist[j] = 0; } }}int isequal(int i) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { if (maze[j][k] != 0 && maze[j][k] != m[i][j][k]) { return 0; } } } return 1;}int main() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { scanf("%d", &maze[i][j]); } } for (int i = 0; i < 8; i++) { if (isequal(i) == 1) { sum++; index = i; } } if (sum == 1) print1(index); else printf("Too Many"); //dfs(0); return 0;}

转载于:https://www.cnblogs.com/woxiaosade/p/10464515.html

你可能感兴趣的文章