[已解决]神奇的幻方

与琪热恋

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

1. #include<iostream>
   
2. #include <fstream>
   
3. #include<string>
   
4. #include <vector>
   
5. 
   
6. using namespace std;
   
7. 
   
8. class MagicSquare
   
9. {
   
10. public:
    
11.     MagicSquare() = delete;
    
12.     MagicSquare(MagicSquare&) = delete;
    
13.     MagicSquare(MagicSquare&&) = delete;
    
14.     MagicSquare(int len) : len(len)
    
15.     {
    
16.         CreateSquare();
    
17.     }
    
18. 
    
19.     void PrintSquare()
    
20.     {
    
21.         for (int i = 0; i < len; ++i)
    
22.         {
    
23.             for (int j = 0; j < len; j++)
    
24.             {
    
25.                 printf_s("%3d ", square[i * len + j]);
    
26.             }
    
27.             printf_s("\n");
    
28.         }
    
29.     }
    
30. 
    
31. private:
    
32.     void CreateSquare()
    
33.     {
    
34.         square = new int[len * len * sizeof(int)];
    
35.         memset(square, 0, len * len * sizeof(int));
    
36. 
    
37.         judgeArr = new int[len * len * sizeof(int)];
    
38.         memset(judgeArr, 0, len * len * sizeof(int));
    
39. 
    
40.         //w 列  h 行
    
41.         int w = len / 2, h = 0;
    
42.         //已经填充的数量
    
43.         int total = 0;
    
44.         //填充数字
    
45.         int num = 1;
    
46. 
    
47.         while (total < len * len)
    
48.         {
    
49.             square[h * len + w] = num;
    
50.             judgeArr[h * len + w] = 1;
    
51.             int prevW = w;
    
52.             int prevH = h;
    
53. 
    
54.             h--;
    
55.             w++;
    
56.             total++;
    
57.             num++;
    
58. 
    
59.             //下个位置已经填过值 或 超出范围
    
60.             while (w >= len || h < 0 || judgeArr[h * len + w] == 1)
    
61.             {
    
62.                 int time = 0;
    
63.                 if (w >= len)
    
64.                     w = 0;
    
65.                 if (h < 0)
    
66.                     h = len - 1;
    
67. 
    
68.                 if (judgeArr[h * len + w] == 1)
    
69.                 {
    
70.                     //回溯
    
71.                     w = prevW;
    
72.                     h = prevH;
    
73.                     
    
74.                     if (time == 0)
    
75.                         h++;
    
76.                     else
    
77.                     {
    
78.                         h--, w++;
    
79.                     }
    
80.                     prevW = w;
    
81.                     prevH = h;
    
82.                     time++;
    
83.                 }
    
84.             }
    
85.         }
    
86.     }
    
87. 
    
88.     //幻方边长
    
89.     int len;
    
90.     //幻方
    
91.     int* square;
    
92.     //判断当前位置是否已经存在值的数组
    
93.     int* judgeArr;
    
94. };
    
95. 
    
96. int main()
    
97. {
    
98.     MagicSquare ms(5);
    
99.     ms.PrintSquare();
    
100. 
     
101.     return 0;
     
102. }

复制代码

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

跳转到最佳答案楼层

yuxijian2020

1. #include<iostream>
   
2. #include <fstream>
   
3. #include<string>
   
4. #include <vector>
   
5. 
   
6. using namespace std;
   
7. 
   
8. class MagicSquare
   
9. {
   
10. public:
    
11.     MagicSquare() = delete;
    
12.     MagicSquare(MagicSquare&) = delete;
    
13.     MagicSquare(MagicSquare&&) = delete;
    
14.     MagicSquare(int len) : len(len)
    
15.     {
    
16.         CreateSquare();
    
17.     }
    
18. 
    
19.     void PrintSquare()
    
20.     {
    
21.         for (int i = 0; i < len; ++i)
    
22.         {
    
23.             for (int j = 0; j < len; j++)
    
24.             {
    
25.                 printf_s("%3d ", square[i * len + j]);
    
26.             }
    
27.             printf_s("\n");
    
28.         }
    
29.     }
    
30. 
    
31. private:
    
32.     void CreateSquare()
    
33.     {
    
34.         square = new int[len * len * sizeof(int)];
    
35.         memset(square, 0, len * len * sizeof(int));
    
36. 
    
37.         judgeArr = new int[len * len * sizeof(int)];
    
38.         memset(judgeArr, 0, len * len * sizeof(int));
    
39. 
    
40.         //w 列  h 行
    
41.         int w = len / 2, h = 0;
    
42.         //已经填充的数量
    
43.         int total = 0;
    
44.         //填充数字
    
45.         int num = 1;
    
46. 
    
47.         while (total < len * len)
    
48.         {
    
49.             square[h * len + w] = num;
    
50.             judgeArr[h * len + w] = 1;
    
51.             int prevW = w;
    
52.             int prevH = h;
    
53. 
    
54.             h--;
    
55.             w++;
    
56.             total++;
    
57.             num++;
    
58. 
    
59.             //下个位置已经填过值 或 超出范围
    
60.             while (w >= len || h < 0 || judgeArr[h * len + w] == 1)
    
61.             {
    
62.                 int time = 0;
    
63.                 if (w >= len)
    
64.                     w = 0;
    
65.                 if (h < 0)
    
66.                     h = len - 1;
    
67. 
    
68.                 if (judgeArr[h * len + w] == 1)
    
69.                 {
    
70.                     //回溯
    
71.                     w = prevW;
    
72.                     h = prevH;
    
73.                     
    
74.                     if (time == 0)
    
75.                         h++;
    
76.                     else
    
77.                     {
    
78.                         h--, w++;
    
79.                     }
    
80.                     prevW = w;
    
81.                     prevH = h;
    
82.                     time++;
    
83.                 }
    
84.             }
    
85.         }
    
86.     }
    
87. 
    
88.     //幻方边长
    
89.     int len;
    
90.     //幻方
    
91.     int* square;
    
92.     //判断当前位置是否已经存在值的数组
    
93.     int* judgeArr;
    
94. };
    
95. 
    
96. int main()
    
97. {
    
98.     MagicSquare ms(5);
    
99.     ms.PrintSquare();
    
100. 
     
101.     return 0;
     
102. }

复制代码

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

yuxijian2020

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. struct Point
   
7. {
   
8.     int x;
   
9.     int y;
   
10.     Point() : x(0), y(0) {}
    
11.     Point(int x, int y) : x(x), y(y) {}
    
12. };
    
13. 
    
14. class MagicSquare
    
15. {
    
16. public:
    
17.     MagicSquare() = delete;
    
18.     MagicSquare(MagicSquare&) = delete;
    
19.     MagicSquare(MagicSquare&&) = delete;
    
20.     explicit MagicSquare(int len) : len(len)
    
21.     {
    
22.         CreateSquare();
    
23.     }
    
24. 
    
25.     ~MagicSquare()
    
26.     {
    
27.         if (judgeArr)
    
28.             delete[] judgeArr;
    
29.         if (square)
    
30.             delete[] square;
    
31.         len = 0;
    
32.     }
    
33. 
    
34.     void PrintSquare()
    
35.     {
    
36.         for (int i = 0; i < len; ++i)
    
37.         {
    
38.             for (int j = 0; j < len; j++)
    
39.             {
    
40.                 printf_s("%3d ", square[i * len + j]);
    
41.             }
    
42.             printf_s("\n");
    
43.         }
    
44.     }
    
45. 
    
46.     int GetNumberByPoint(Point p) { return square[p.x * len + p.y]; }
    
47. 
    
48. private:
    
49.     void CreateSquare()
    
50.     {
    
51.         square = new int[len * len * sizeof(int)];
    
52.         memset(square, 0, len * len * sizeof(int));
    
53. 
    
54.         judgeArr = new int[len * len * sizeof(int)];
    
55.         memset(judgeArr, 0, len * len * sizeof(int));
    
56. 
    
57.         //w 列  h 行
    
58.         int w = len / 2, h = 0;
    
59.         //已经填充的数量
    
60.         int total = 0;
    
61.         //填充数字
    
62.         int num = 1;
    
63. 
    
64.         while (total < len * len)
    
65.         {
    
66.             square[h * len + w] = num;
    
67.             judgeArr[h * len + w] = 1;
    
68.             int prevW = w;
    
69.             int prevH = h;
    
70. 
    
71.             h--;
    
72.             w++;
    
73.             total++;
    
74.             num++;
    
75. 
    
76.             //下个位置已经填过值 或 超出范围
    
77.             while (w >= len || h < 0 || judgeArr[h * len + w] == 1)
    
78.             {
    
79.                 int time = 0;
    
80.                 if (w >= len)
    
81.                     w = 0;
    
82.                 if (h < 0)
    
83.                     h = len - 1;
    
84. 
    
85.                 if (judgeArr[h * len + w] == 1)
    
86.                 {
    
87.                     //回溯
    
88.                     w = prevW;
    
89.                     h = prevH;
    
90.                     
    
91.                     if (time == 0)
    
92.                         h++;
    
93.                     else
    
94.                     {
    
95.                         h--, w++;
    
96.                     }
    
97.                     prevW = w;
    
98.                     prevH = h;
    
99.                     time++;
    
100.                 }
     
101.             }
     
102.         }
     
103.     }
     
104. 
     
105.     //幻方边长
     
106.     int len;
     
107.     //幻方
     
108.     int* square;
     
109.     //判断当前位置是否已经存在值的数组
     
110.     int* judgeArr;
     
111. };
     
112. 
     
113. vector<int> GetInputAndResult()
     
114. {
     
115.     int len = 0, sum = 0;
     
116.    
     
117.     while (len % 2 == 0 || sum > len * len)
     
118.     {
     
119.         printf_s("请输入幻方阶数(奇数)和被污染的格子数:");
     
120.         scanf_s("%d%*c%d%*c", &len, &sum);
     
121.         
     
122.         if (len % 2 == 0)
     
123.         {
     
124.             printf_s("幻方的阶数必须为奇数!\n");
     
125.             continue;
     
126.         }
     
127. 
     
128.         if (sum > len * len)
     
129.         {
     
130.             printf_s("被污染的格子数超过了总格子数!\n");
     
131.             continue;
     
132.         }
     
133.     }
     
134. 
     
135.     MagicSquare ms(len);
     
136.     Point p;
     
137.     vector<int> result;
     
138. 
     
139.     for (int i = 0; i < sum; ++i)
     
140.     {
     
141.         printf("请输入第 %d 个被污染的格子坐标：", i + 1);
     
142.         scanf_s("%d%*c%d%*c", &p.x, &p.y);
     
143.         //坐标超出范围
     
144.         if ((p.x < 1 || p.x > len) && (p.y < 1 || p.y > len))
     
145.         {
     
146.             i--;
     
147.             continue;
     
148.         }
     
149. 
     
150.         p.x--, p.y--;
     
151.         result.push_back(ms.GetNumberByPoint(p));
     
152.     }
     
153. 
     
154.     return result;
     
155. }
     
156. 
     
157. int main()
     
158. {
     
159.     vector<int> result(GetInputAndResult());
     
160. 
     
161.     for (const auto& i : result) { printf_s("%d\n", i); }
     
162. 
     
163.     return 0;
     
164. }

复制代码