Re: [ACM] 拋磚引玉 - Chessboard

[chchwy (mat)]

黑貓沒有把題目描述得很詳細
看英文題目有幾點要釐清

首先這題要算的是路徑的「長度」 而不是「走幾步」
here we mean the length of the polyline, not the number of king's moves

每一個格子「一定」要走一次，也只能走一次
Each cell must be visited exactly once;

最後一步跟第一步必須是同一格，也就是最後一步要繞一圈回到起始位置
the first and the last cells of the path must coincide

比如說
2x2棋盤有4格 一定剛好走4步 最後一步回到起始位置

我提供一點想法

因為步數永遠固定
但是旗子可以往八個方向走 走直的走斜的都行
直線一步 路徑長度+1
而走斜線一步 路徑長度+根號2

所以解法上
能夠走越多步斜線 路徑就越長

目前推到n=5 還沒看出什麼規律....


※ 引述《cair (白色的黑貓)》之銘言：
: 來點ACM題目大家互相討論好了
: 只需寫出想法及作法 不需附上程式
: ==========================================
: Chessboard
: 給一個 n*n 的棋盤，  ( 1<= n <= 300 )
: 你可以從棋盤上任一點開始，
: 以八相鄰的方式移動。
: 每一個格子只能走一次，
: 而且移動的路徑不能出現跨線(即不可路徑有重疊或是跨過之前路徑)，
: 並回到原點，求此路徑的最長可能距離。
: 時間限制:100ms
: 題目原文
: http://acm.uva.es/p/v107/10751.html
: 提示:範圍在10*10以內還可以暴力解 但是因為數字很大並且有時間限制
: 因此必須找出計算公式~
※ 引述《cair (白色的黑貓)》之銘言：
: 來點ACM題目大家互相討論好了
: 只需寫出想法及作法 不需附上程式
: ==========================================
: Chessboard
: 給一個 n*n 的棋盤，  ( 1<= n <= 300 )
: 你可以從棋盤上任一點開始，
: 以八相鄰的方式移動。
: 每一個格子只能走一次，
: 而且移動的路徑不能出現跨線(即不可路徑有重疊或是跨過之前路徑)，
: 並回到原點，求此路徑的最長可能距離。
: 時間限制:100ms
: 題目原文
: http://acm.uva.es/p/v107/10751.html
: 提示:範圍在10*10以內還可以暴力解 但是因為數字很大並且有時間限制
: 因此必須找出計算公式~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.112.163.224
推 linjrming:把"格子"想成點會好想很多
推 cair:對  我是這樣作圖的  因為懶...
→ cair:不過很多題目喜歡用西洋棋盤類型來描述
→ chchwy:我找出規律了 不過這個有辦法證明嗎XDDD
推 cair:跟我一樣畫滿白紙當證明 XDDD
推 s4511981:規律就是(N*4-4)+(N-2)^2*根號二...為什麼 囧?
→ s4511981:找到規律無法證明(／‵Д′)／~ ╧╧