CodeForces-710C Magic Odd Square(幻方问题/构造)

C. Magic Odd Squaretime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Find an n × n matrix with different numbers from 1 to n2, so the sum in each row, column and both main diagonals are odd.

Input

The only line contains odd integer n (1 ≤ n ≤ 49).

Output

Print n lines with n integers. All the integers should be different and from 1 to n2. The sum in each row, column and both main diagonals should be odd.

Examplesinput

1

output

1

input

3

output

2 1 4
3 5 7
6 9 8

题意:给出n*n的空矩阵,要求用[1,n*n]构造出每一行,每一列,2条对角线的数之和都是奇数的矩阵(每个格子的数要不相同)

题解:可以推断出n一定是奇数,我们先将矩阵的正中间列和正中间行全部填上奇数,令n=2*k+1(k>=1),剩下的奇数个数m=(n*n+1)/2-2*n+1,化简得到m=2k(k-1),因为k>=1,所以m一定是4的倍数,于是可以知道,我们只要同时把关于正中间线对称的4个点变成奇数,整个矩阵还是合法的.

#include<cstdio>
#include<algorithm>
using namespace std;
int mp[55][55];
int main(){
int n;
scanf("%d",&n);
if(n==1) {printf("1\n");return 0;}
int mid=(n+1)/2,num=(n*n+1)/2-2*n+1;

for(int i=1;i<=n;i++) mp[i][mid]=mp[mid][i]=1;
bool flag;
while(num>0){
num-=4;
flag=0;
for(int i=1;i<=n;i++){
if(flag) break;
for(int j=1;j<=n;j++){
if(mp[i][j]==0){
mp[i][j]=mp[n-i+1][j]=mp[i][n-j+1]=mp[n-i+1][n-j+1]=1;
flag=1;
break;
}
}
}
}
int odd=1,even=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mp[i][j]) printf("%d%c",odd*2-1,j==n?'\n':' '),odd++;
else printf("%d%c",even*2,j==n?'\n':' '),even++;
return 0;