ZH-Y-Q查看:0 回复:1 评论:0 创建时间:2020-05-17T09:32:33用户:
题目描述
给一个n*n的方格矩阵，还有n*n个整数，让你将这些整数填入矩阵，使得每行每列每个对角线上整数的和都相等。下面给出几个例子：
输入
第一行一个整数n(1<=n<=4)
第二行n*n个整数ai(-10^8<=ai<=10^8)
输出第一行一个整数s 代表每行每列每个对角线的和值
接下来输出一个n*n的矩阵，表示填数方案。
数据保证有解，可能存在多种方案，输出字典序最小的（将每行顺次相连之后，字典序最小）
样例输入3
1 2 3 4 5 6 7 8 9 样例输出
15
2 7 6
9 5 1
4 3 8
ZH-Y-Q#include<bits/stdc++.h>
using namespace std;
int n,a[101],z,f[101],ans[11][11];
void dfs(int x,int y){
if(x==n&&y==n+1){
cout<<z<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j==n)cout<<ans[i][j]<<endl;
else cout<<ans[i][j]<<" ";
}
}
exit(0);
}
if(y>n){
dfs(x+1,1);
return;
}
for(int i=1;i<=n*n;i++){
if(f[i]==0){ //第i这个数未使用
if(y==n){ //该行数字和判断
int u=a[i];
for(int j=1;j<n;j++)
u+=ans[x][j];
if(u!=z)continue;
}
if(x==n){ //该列数字和判断
int u=a[i];
for(int j=1;j<n;j++)
u+=ans[j][y];
if(u!=z)continue;
}
if(x==n&&y==1){ //斜线（右上角到左下角
int u=a[i];
for(int j=1;j<n;j++)
u+=ans[j][n-j+1];
if(u!=z)continue;
}
if(x==n&&y==n){ //斜线（右上角到左下角
int u=a[i];
for(int j=1;j<n;j++)
u+=ans[j][j];
if(u!=z)continue;
}
f[i]=1; //标记
ans[x][y]=a[i]; //填数
dfs(x,y+1);
f[i]=0;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n*n;i++){
cin>>a[i];
z+=a[i];
}
z/=n;
sort(a+1,a+n*n+1);
dfs(1,1);
return 0;
}点赞0
评论