作者chchwy (mat)
看板NTUE-CS100
標題Re: [ACM] 拋磚引玉 - Chessboard
時間Tue Jul 29 19:52:13 2008
黑貓沒有把題目描述得很詳細
看英文題目有幾點要釐清
首先這題要算的是路徑的「長度」 而不是「走幾步」
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
1F：推 linjrming:把"格子"想成點會好想很多 07/29 19:58
2F：推 cair:對 我是這樣作圖的 因為懶... 07/29 20:00
3F：→ cair:不過很多題目喜歡用西洋棋盤類型來描述 07/29 20:01
4F：→ chchwy:我找出規律了 不過這個有辦法證明嗎XDDD 07/29 20:08
5F：推 cair:跟我一樣畫滿白紙當證明 XDDD 07/29 20:29
6F：推 s4511981:規律就是(N*4-4)+(N-2)^2*根號二...為什麼 囧? 07/29 23:11
7F：→ s4511981:找到規律無法證明(／‵Д′)／~ ╧╧ 07/29 23:22