題目不是很好懂= =。

給你一個 n方陣,你要構造出多個步驟 (k, X1, X2, X3....),使得 每步驟 玩家都可以 走k步後 把 X1, X2, X3, X4 刪掉,玩家走到的點(僅終點)不能被刪掉 且 被刪掉的點不能再走。

最後要剩下 1 個點沒被刪掉(也就是玩家最後在的那個點)。

看過很多題解,每個人的 構造法 都不同,我的這個應該算短的吧。

1. 一開始一定要走 n 步,這時候先把 與 1 距離 >n 的點 刪掉。

2. 把 方陣 想像成 黑白染色,就是相鄰不同色。

    只要走 奇數步,起終點不同色,反之 偶數步 則同色。

    如果 n=奇數,則 走完n步,一定不同色。

    如果 n=偶數,則為同色。

    由於構造原理,需要每次都走到不同色上,所以除了一開始以外,都要走奇數步。

3. 走完 奇數部數 後,把 方陣 順轉 45 來看,把還沒被刪掉的最後一排刪掉。 <其實就是不斷的從右下角,往上一直刪>

4. 重複 步驟3 ,即可把 方陣 刪到只剩 左上方的 1。

 

讓我們來想想原理,分成 n 的奇偶來討論。

if(n%2 == 0)

n是偶數,所以 步驟1 走完 n 步後會同色,並且 步驟1 刪完後 最右下那一排也是同色 (順轉45)。

也就是說如果 你接下來不斷走 奇數步,也就會不斷的刪掉你 不可能 走到的那一排。

由於是從 右下往上 刪,所以也不會有 走到一個點後斷層(走不回其他沒被刪到的點) 的情況發生。

if(n%2 == 1)

與偶數差不多,一開始會走到不同色,留下不同色那排。

然後就跟偶數情況一樣了。

最後是 特判,n=2的情況不適用。

 

結論:

利用走 奇數步 會到不同色的特性,可以不斷地從 右下角 刪,直到 剩下左上角的 1。

我的code

http://snipt.org/zfggb6

 

創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()