前往
大廳
主題

ZeroJudge - c153: NOIP2015 Day1.1.神奇的幻方 解題心得

Not In My Back Yard | 2021-08-11 00:00:05 | 巴幣 100 | 人氣 249

題目連結:


題目大意:
(原題因為是對岸之題目,所以「行」、「列」之概念恰好與臺灣的相反。以下使用臺灣的直行橫列之標準)

輸入給定一正整數 N(1 ≦ N ≦ 39,且 N 為奇數)。請按照以下方式生成一個 N × N 之幻方(Magic Square):
將整數 1 放在第一列的正中間;然後按照以下情況填入剩下的數字 K = 2 、 3 、 …… 、 N × N:
1.如果整數 K - 1 不在第一列也不在最後一行,則看其右上角之位置是否已填有數字。如果沒有,就將整數 K 填到 K - 1 的右上角;反之則填到 K - 1 的正下方。
2.如果整數 K - 1 在第一列但不在最後一行,則將整數  K 填到最後一列、K - 1 所在行右邊一行的位置;
3.如果整數 K - 1 在最後一行但不在第一列,則將整數  K 填到第一行、K - 1 所在列上面一列的位置;
4.如果整數 K - 1 在第一列最後一行,則將整數 K 填到 K - 1 的正下方之位置。



範例輸入:
3


範例輸出:
8 1 6
3 5 7
4 9 2


解題思維:
模擬即可。

不過實際上題目給定的生成演算法等價於以下方式:
同樣地,先將整數 1 放在第一列的正中間;而對於其他數字 K:
判斷 K - 1 的右上角,也就是往上一列、往右一行(往上出界了則繞回最後一列、往右出界則繞回第一行。使用取餘操作即可輕鬆求出行列位置值)的位置有沒有被填過數字。如果沒有就將 K 填到該位置;反之則填 K - 1 的正下方之位置。

因此判斷條件可以大幅地減少(也比較不容易出錯)。最後輸出幻方的內容即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作