题干：

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 ;
}