问题描述

幻方(magic square)是一个非常有趣的矩阵，n 阶的幻方表示一个 n 阶矩阵它的元素恰好是 1~N^2，它的各行，各列，以及对角线之和都相等。下面是一非常经典的 3 阶幻方：2 7 6 9 5 1 4 3 8 你的任务是找出字典序第 K 小的 4 阶幻方。

这里的幻方的字典序定义为：把幻方按行优先排成一条 N^2 的序列后的典序(如上面这个幻方，排成这样一条序列：2 7 6 9 5 1 4 38)。其中 K<=100。字典序的定义为：在某一系列字符串中，首先按照第一个字符明确其先后序，如果第一个字符相同，则根据第二个字符的大小关系明确其先后关系。以类推。例如： 1 2 3 4 5 6 7 8 9 10 11 在 2 1 3 4 5 6 7 8 9 10 11 之前 1 2 3 4 5 7 8 9 10 11 在 1 3 2 4 5 6 7 8 9 10 11 之前输入格式输入仅包含一行 K。

输出格式

4 行 4 列的幻方，数之间用一个空格隔开，行末不要有多余的空格。

样例输入

1

样例输出

1 2 15 16
12 14 3 5
13 7 10 4
8 11 6 9

TLE 0pts 代码

#include<iostream>
using namespace std;
int ans[10][10];
bool vst[20];
int k,cnt;
void dfs(int x,int y){
	if(x==5){
		int s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,s7=0,s8=0,s9=0,s10=0;
		for(int i=1;i<=4;i++){
			s1+=ans[1][i],s2+=ans[2][i],s3+=ans[3][i],s4+=ans[4][i];
			s5+=ans[i][1],s6+=ans[i][2],s7+=ans[i][3],s8+=ans[i][4];
			s9+=ans[i][i],s10+=ans[i][4-i+1];                                                                                   
		}
		if(s1==s2&&s2==s3&&s3==s4&&s4==s5&&s5==s6&&s6==s7&&s7==s8&&s8==s9&&s9==s10) cnt++;
		if(cnt==k){
			for(int i=1;i<=4;i++){
				for(int j=1;j<=4;j++){
					cout<<ans[i][j]<<" ";
				}
				cout<<endl;
			}
		}
	}
	for(int i=1;i<=16;i++){
		if(vst[i]==false){
			vst[i]=true;
			ans[x][y]=i;
			if(y+1<=4) dfs(x,y+1);
			else dfs(x+1,1);
			vst[i]=false;
		}
	}
}
int main(){
	cin>>k;
	dfs(1,1);
	return 0;
}