題干：

C語言_魔方陣

描述

?

魔方陣是一個古老的智力問題，它要求在一個m×m的矩陣中填入1～m2的數字（m為奇數），使得每一行、每一列、每條對角線的累加和都相等，如下為5階魔方陣示例。

15 8 1 24 17

???? ? ? ??16 14 7 5 23

?22 20 13 6 4

?3 21 19 12 10

?9 2 25 18 11

?

?

輸入

?

輸入一個數n，表示矩陣的大小，保證n<100且n為奇數

?

輸出

?

輸出一個矩陣，每個元素之間以一個空格分隔

答案不唯一，輸出一個題目要求的矩陣即可

?

輸入樣例 1?

5

輸出樣例 1

15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11

?

解題報告：

? 可以找到規律構造，以（1，n/2+1）這個點為1，然后向左上擴展，如果最上面了就循環到最下面，如果到最左邊了就循環到最右邊，如果該點被填過值了，那就到他下面那個點，然后就可以構造出這個圖形了。

剛開始是用搜索寫的：

#include<bits/stdc++.h>using namespace std; int n,flag,sum; bool vis[505]; int maze[505][505]; bool fitr1(int x) {int res = 0;for(int i = 1; i<=n; i++) {res += maze[x][i];}if(res != sum) return 0;else return 1; } bool fitr2(int x ,int y){int res = 0;for(int i = 1; i<=y; i++) {res += maze[x][i];}if(res >= sum) return 0;else return 1;} bool dui(int x,int y) {int res = 0;for(int i = 1; i<=x; i++) {res += maze[i][i];}if(res >sum ) return 0;res = 0;for(int i = 1; i<=x; i++) {res += maze[i][n-i+1];}if(res >sum ) return 0;return 1; } bool fitc(int x,int y) {int res = 0;for(int i = 1; i<=x; i++) {res += maze[i][y];}if(res > sum) return 0;else return 1; } bool ff() {int resr[105] = {0},resc[105] = {0},res = 0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {resr[i] += maze[i][j];resc[j] += maze[i][j];}}for(int i = 1; i<=n; i++) {if(resr[i] != sum || resc[i] != sum) return 0;}//for(int i = 1; i<=n; i++) res += maze[i][i];if(res != sum ) return 0;res = 0;for(int i = 1; i<=n; i++) res += maze[i][n-i+1];if(res != sum ) return 0;return 1; } void dfs(int x,int y) { // printf("x = %d y = %d\n",x,y);if(x == n+1) {if(ff()) flag = 1;return ;}if(flag == 1) return ;for(int i = 1; i<=n*n; i++) {if(vis[i]) continue;maze[x][y] = i;if(flag == 1) return ;if(x == y) {if(!dui(x,y)) continue;} // if(!fitc(x,y)) continue;if(y == n) { // if(!fitr1(x)) continue;vis[i] = 1;dfs(x+1,1);if(flag == 1) return ;vis[i] = 0;}else { // if(!fitr2(x,y)) continue;vis[i]=1;dfs(x,y+1);if(flag == 1) return ;vis[i] = 0;}} } int main() {cin>>n;for(int i = 1; i<=n*n; i++) {sum += i;}sum/=n;dfs(1,1);for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {printf("%d%c",maze[i][j],j==n ? '\n' : ' ');}}return 0 ; }

然而發現只能輸入3的時候輸出，輸入5的時候就跑不出來了。最后一項也是，9^15次方，肯定跑不出來呀。

AC代碼：

#include<cstdio> #include<queue> #include<string> #include<cstring> #include<cmath> #include<map> #include<iostream> #include<algorithm> #define ll long long const ll mod = 1e9+7; using namespace std; int maze[105][105]; int main() {int n;cin>>n;maze[1][(n+1)/2] = 1;int cur=2,tmp = n;int x = 1,y = (n+1)/2;while(cur <= n*n) {if(x == 1) {if(y == 1) {maze[x+1][y] = cur++;x++;tmp = n;continue;}else {for(int i = 1; i<=n; i++) {if(maze[tmp][y-1] != 0) tmp--;else break;}maze[tmp][y-1] = cur++;x=tmp;y--;tmp = n;}}else if(y == 1) {for(int i = 1; i<=n; i++) {if(maze[x-1][tmp] != 0) tmp--;else break;}maze[x-1][tmp] = cur++;x--;y=tmp;tmp=n;}else if(maze[x-1][y-1] != 0 ) {maze[x+1][y] = cur++;x++;}else {maze[x-1][y-1] = cur++;x--,y--;}}for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {printf("%d%c",maze[i][j],j == n ? '\n' : ' ');}}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【qduoj】奇数阶幻方 （构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。