P1978神奇的幻方 Accepted 标簽: NOIP提高組2015
描述
幻方是一種很神奇的 N ∗ N 矩陣:它由數字 1,2,3, … … , N ∗ N 構成,且每行、每列及兩條對角線上的數字之和都相同。
當 N 為奇數時,我們可以通過以下方法建構一個幻方: 首先将 1 寫在第一行的中間。
之後,按如下方式從小到大依次填寫每個數 K(K = 2,3, … , N ∗ N) :
- 若 (K − 1) 在第一行但不在最後一列,則将 K 填在最後一行, (K − 1) 所在列的右一列;
- 若 (K − 1) 在最後一列但不在第一行,則将 K 填在第一列,(K − 1) 所在行的上一行;
- 若 (K − 1) 在第一行最後一列,則将 K 填在 (K − 1) 的正下方;
- 若 (K − 1) 既不在第一行,也不在最後一列,如果 (K − 1) 的右上方還未填數, 則将 K 填在(K − 1)的右上方,否則将 K 填在 (K − 1) 的正下方。
現給定 N,請按上述方法構造 N ∗ N 的幻方。
格式
輸入格式
一個整數 N,即幻方的大小。
輸出格式
輸出檔案包含 N 行,每行 N 個整數,即按上述方法構造出的 N ∗ N 的幻方。相鄰兩個整數之間用單個空格隔開。
樣例1
樣例輸入1[複制]
3
樣例輸出1[複制]
8 1 6 3 5 7 4 9 2
限制
對于 100% 的資料,1 ≤ N ≤ 39 且 N 為奇數。
來源
NOIP 2015 提高組 Day 1 第一題
思路
1)其實吧,這個題目的文字描述,就已經把算法寫得很清楚了,基本上每一句話都可以直接翻譯成代碼,隻要熟悉數組的寫法就很容易實作了 2)用a[x][y]=k表示第x行第y列為k,然後就是确定下一個k所在的x,y
代碼
#include <iostream>
using namespace std;
int n,x,y,k,a[40][40];
int main()
{
cin>>n;
a[x=1][y=(n+1)/2]=++k; // 首先将 1 寫在第一行的中間
while(k<=n*n)
{
if(x==1&&y!=n)
a[x=n][++y]=++k; //若(K-1)在第一行但不在最後一列,則将 K 填在最後一行, (K - 1) 所在列的右一列
else if(x!=1&&y==n)
a[--x][y=1]=++k; //若(K-1)在最後一列但不在第一行,則将 K 填在第一列,(K-1)所在行的上一行
else if(x==1&&y==n||a[x-1][y+1])
a[++x][y]=++k; //若(K-1)在第一行最後一列,則将K填在(K-1)的正下方
else
a[--x][++y]=++k; //如果 (K-1) 的右上方還未填數,則将 K 填在(K-1)的右上方,否則将 K填在 (K-1) 的正下方
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<' ';
cout<<endl;
}
return 0;
}
NOIP做題記錄(提高組)