作者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