历届试题 九宫幻方

问题描述   小明最近在教邻居家的小朋友小学奥数,而最近正好讲述到了三阶幻方这个部分,三阶幻方指的是将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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stdlib.h>
#include <cstdlib>
#include <string.h>
#include <string>
#include <cmath>
#include <map>
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;
}

 

上一篇:leetcood学习笔记-79-单词搜索


下一篇:Maze Problem with weight 1 and 2