c153 - NOIP2015 Day1.1.神奇的幻方
題目描述
題目要求根據給定的奇數 N，構造一個 N x N 的幻方。幻方由數字 1 到 N x N 構成，且每行、每列以及兩條對角線上的數字之和都相同。構造方法依照題目描述的規則進行。
解題思路
這題的解題思路是直接模擬題目描述的填數規則。首先，將 1 放在第一行的中間位置。然後，從 2 開始，依序填入數字，每次根據前一個數字的位置，按照四種情況中的一種來確定下一個數字的位置。具體來說，就是檢查前一個數字是否在第一行或最后一列，以及其右上方是否已經填入數字。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n^2)
程式碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,s[51][51],lx,ly;
int main(){
scanf("%d",&n);
lx=1,ly=(n>>1)+1;
s[lx][ly]=1;
int k=n*n;
for(int i=2;i<=k;i++){
if(lx==1&&ly!=n)
lx=n,ly++;
else if(lx!=1&&ly==n)
lx--,ly=1;
else if(lx==1&&ly==n)
lx++;
else if(lx!=1&&ly!=n)
{
if(s[lx-1][ly+1]==0)lx--,ly++;
else lx++;
}
s[lx][ly]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++)
printf("%d ",s[i][j]);
printf("%d\n",s[i][n]);
}
}