[已解决]神奇的幻方

与琪热恋

7岁的小明在科普杂志上看到了关于奇数阶幻方的解法，方法是首先数字 1 放在首行最中间的格子中，然后向右上角斜行，并依次把后续数字填入对应位置。注意特殊情况：
1）如果超出了上边界，就以出框后的虚拟方格位置为基准，将数字（记为 k ）平移至最下行对应的格子中；
2）如果超出了右边界，就以出框后的虚拟方格位置为基准，将 k 平移至最左列对应的格子中；
3）如果右上角格子已被其它数字占领，就将 k填写在数字 k1 所在位置的下方格子中。以此法得出幻方。例如五阶幻方，按此法生成的结果（请忽略表格的第一行），可以注意到，每一行每一列的和，两个对角线的和均为65：
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
现在小明手里有一个幻方，但是不小心把M个格子给污染了。他会告诉你这M个格子的位置，并且想让你告诉他询问的位置对应的数是多少。
输入数据
第一行两个数 N,M(N≤10000,保证N为奇数,M≤100000)
N,M(N≤10000,保证N为奇数,M≤100000)
，表示幻方的阶数和被污染的格子数
接下来 M 行，每行两个数 x,y(1≤x,y≤n) ，表示污染的格子在第x 行，第y列。
输出数据
共M行，每行一个数，为所求位置的数字。
样例输入
5 2
1 3
5 3
样例输出
1
25
求大佬答疑解惑，小白真的不会写

最佳答案

月排行榜 / 总排行榜

yuxijian2020

2021-5-6 12:04:38

#include<iostream>
#include <fstream>
#include<string>
#include <vector>

using namespace std;

class MagicSquare
{
public:
    MagicSquare() = delete;
    MagicSquare(MagicSquare&) = delete;
    MagicSquare(MagicSquare&&) = delete;
    MagicSquare(int len) : len(len)
    {
        CreateSquare();
    }

    void PrintSquare()
    {
        for (int i = 0; i < len; ++i)
        {
            for (int j = 0; j < len; j++)
            {
                printf_s("%3d ", square[i * len + j]);
            }
            printf_s("\n");
        }
    }

private:
    void CreateSquare()
    {
        square = new int[len * len * sizeof(int)];
        memset(square, 0, len * len * sizeof(int));

        judgeArr = new int[len * len * sizeof(int)];
        memset(judgeArr, 0, len * len * sizeof(int));

        //w 列  h 行
        int w = len / 2, h = 0;
        //已经填充的数量
        int total = 0;
        //填充数字
        int num = 1;

        while (total < len * len)
        {
            square[h * len + w] = num;
            judgeArr[h * len + w] = 1;
            int prevW = w;
            int prevH = h;

            h--;
            w++;
            total++;
            num++;

            //下个位置已经填过值 或 超出范围
            while (w >= len || h < 0 || judgeArr[h * len + w] == 1)
            {
                int time = 0;
                if (w >= len)
                    w = 0;
                if (h < 0)
                    h = len - 1;

                if (judgeArr[h * len + w] == 1)
                {
                    //回溯
                    w = prevW;
                    h = prevH;
                    
                    if (time == 0)
                        h++;
                    else
                    {
                        h--, w++;
                    }
                    prevW = w;
                    prevH = h;
                    time++;
                }
            }
        }
    }

    //幻方边长
    int len;
    //幻方
    int* square;
    //判断当前位置是否已经存在值的数组
    int* judgeArr;
};

int main()
{
    MagicSquare ms(5);
    ms.PrintSquare();

    return 0;
}

我只写了创建幻方，剩下的就是输入位置，然后输出数组那个位置的值，没啥玩意  自己写吧

跳转到最佳答案楼层

yuxijian2020

#include<iostream>
#include <fstream>
#include<string>
#include <vector>

using namespace std;

class MagicSquare
{
public:
    MagicSquare() = delete;
    MagicSquare(MagicSquare&) = delete;
    MagicSquare(MagicSquare&&) = delete;
    MagicSquare(int len) : len(len)
    {
        CreateSquare();
    }

    void PrintSquare()
    {
        for (int i = 0; i < len; ++i)
        {
            for (int j = 0; j < len; j++)
            {
                printf_s("%3d ", square[i * len + j]);
            }
            printf_s("\n");
        }
    }

private:
    void CreateSquare()
    {
        square = new int[len * len * sizeof(int)];
        memset(square, 0, len * len * sizeof(int));

        judgeArr = new int[len * len * sizeof(int)];
        memset(judgeArr, 0, len * len * sizeof(int));

        //w 列  h 行
        int w = len / 2, h = 0;
        //已经填充的数量
        int total = 0;
        //填充数字
        int num = 1;

        while (total < len * len)
        {
            square[h * len + w] = num;
            judgeArr[h * len + w] = 1;
            int prevW = w;
            int prevH = h;

            h--;
            w++;
            total++;
            num++;

            //下个位置已经填过值 或 超出范围
            while (w >= len || h < 0 || judgeArr[h * len + w] == 1)
            {
                int time = 0;
                if (w >= len)
                    w = 0;
                if (h < 0)
                    h = len - 1;

                if (judgeArr[h * len + w] == 1)
                {
                    //回溯
                    w = prevW;
                    h = prevH;
                    
                    if (time == 0)
                        h++;
                    else
                    {
                        h--, w++;
                    }
                    prevW = w;
                    prevH = h;
                    time++;
                }
            }
        }
    }

    //幻方边长
    int len;
    //幻方
    int* square;
    //判断当前位置是否已经存在值的数组
    int* judgeArr;
};

int main()
{
    MagicSquare ms(5);
    ms.PrintSquare();

    return 0;
}

我只写了创建幻方，剩下的就是输入位置，然后输出数组那个位置的值，没啥玩意  自己写吧

yuxijian2020

#include <iostream>
#include <vector>

using namespace std;

struct Point
{
    int x;
    int y;
    Point() : x(0), y(0) {}
    Point(int x, int y) : x(x), y(y) {}
};

class MagicSquare
{
public:
    MagicSquare() = delete;
    MagicSquare(MagicSquare&) = delete;
    MagicSquare(MagicSquare&&) = delete;
    explicit MagicSquare(int len) : len(len)
    {
        CreateSquare();
    }

    ~MagicSquare()
    {
        if (judgeArr)
            delete[] judgeArr;
        if (square)
            delete[] square;
        len = 0;
    }

    void PrintSquare()
    {
        for (int i = 0; i < len; ++i)
        {
            for (int j = 0; j < len; j++)
            {
                printf_s("%3d ", square[i * len + j]);
            }
            printf_s("\n");
        }
    }

    int GetNumberByPoint(Point p) { return square[p.x * len + p.y]; }

private:
    void CreateSquare()
    {
        square = new int[len * len * sizeof(int)];
        memset(square, 0, len * len * sizeof(int));

        judgeArr = new int[len * len * sizeof(int)];
        memset(judgeArr, 0, len * len * sizeof(int));

        //w 列  h 行
        int w = len / 2, h = 0;
        //已经填充的数量
        int total = 0;
        //填充数字
        int num = 1;

        while (total < len * len)
        {
            square[h * len + w] = num;
            judgeArr[h * len + w] = 1;
            int prevW = w;
            int prevH = h;

            h--;
            w++;
            total++;
            num++;

            //下个位置已经填过值 或 超出范围
            while (w >= len || h < 0 || judgeArr[h * len + w] == 1)
            {
                int time = 0;
                if (w >= len)
                    w = 0;
                if (h < 0)
                    h = len - 1;

                if (judgeArr[h * len + w] == 1)
                {
                    //回溯
                    w = prevW;
                    h = prevH;
                    
                    if (time == 0)
                        h++;
                    else
                    {
                        h--, w++;
                    }
                    prevW = w;
                    prevH = h;
                    time++;
                }
            }
        }
    }

    //幻方边长
    int len;
    //幻方
    int* square;
    //判断当前位置是否已经存在值的数组
    int* judgeArr;
};

vector<int> GetInputAndResult()
{
    int len = 0, sum = 0;
    
    while (len % 2 == 0 || sum > len * len)
    {
        printf_s("请输入幻方阶数(奇数)和被污染的格子数:");
        scanf_s("%d%*c%d%*c", &len, &sum);
        
        if (len % 2 == 0)
        {
            printf_s("幻方的阶数必须为奇数!\n");
            continue;
        }

        if (sum > len * len)
        {
            printf_s("被污染的格子数超过了总格子数!\n");
            continue;
        }
    }

    MagicSquare ms(len);
    Point p;
    vector<int> result;

    for (int i = 0; i < sum; ++i)
    {
        printf("请输入第 %d 个被污染的格子坐标：", i + 1);
        scanf_s("%d%*c%d%*c", &p.x, &p.y);
        //坐标超出范围
        if ((p.x < 1 || p.x > len) && (p.y < 1 || p.y > len))
        {
            i--;
            continue;
        }

        p.x--, p.y--;
        result.push_back(ms.GetNumberByPoint(p));
    }

    return result;
}

int main()
{
    vector<int> result(GetInputAndResult());

    for (const auto& i : result) { printf_s("%d\n", i); }

    return 0;
}