V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
stefanzweig
V2EX  ›  问与答

请问一个算法题,关于填格子的。

  •  
  •   stefanzweig · 2012-11-21 20:42:04 +08:00 · 3474 次点击
    这是一个创建于 4396 天前的主题,其中的信息可能已经有所发展或是发生改变。
    大家好。非常冒昧到这里来问一道算法题。

    我有一个棋盘,10×10大小的。现在我要依次在格子内放棋子,棋子有编号的,1 到 100。

    要求是:
    1. 编号为1的棋子只能放在最左上角的格子里。接下里一次放相应编号的棋子。
    2. 接下来的棋子可以水平相隔两个格子或者竖直相隔两个格子放入。或者……
    3. 接下来的棋子可以在对角线的线路上放,和上次的棋子相隔一个格子。
    4. 目的是100个棋子都能放进棋盘。

    问题是按照这个规则能有多少种结果。用程序怎么实现呢?

    我自己简化过问题到5×5,包括可以重复的组合一共有500+种结果。但是同样的程序跑6×6已经一个多小时出不来结果了。我想知道在算法上应该选择什么样的策略。谢谢。
    4 条回复    1970-01-01 08:00:00 +08:00
    laskuma
        1
    laskuma  
       2012-11-22 00:05:40 +08:00
    要求有点没看懂 2 3条件是任何时刻选一个满足?还是说只能交替满足?另外3有点没看懂
    laskuma
        2
    laskuma  
       2012-11-22 02:04:08 +08:00
    我算法不好…问了@abccb1 表示用DFS或者直接数学方法解
    fanzeyi
        3
    fanzeyi  
       2012-11-22 02:18:27 +08:00
    感觉可能是动态规划,目测不在能力范围内

    大概想了下状态 f[i][j] 表示 (i,j) 格子(左上为 (0,0))的结果..

    === 以上删除 ===

    尝试写动态转移方程的时候发现,还可以竖直放,也就是说第 (i,j) 格子可以从 (i+1,j)个格子放过来…… 所以不满足动态规划的无后效性……

    或者是比较高级的动态规划…… 不会呢

    (其他同学继续想吧…… )
    qiukun
        4
    qiukun  
       2012-11-22 08:50:48 +08:00
    将起点和终点连接起来。就是寻找汉密尔顿回路的问题。http://zh.wikipedia.org/zh/%E5%93%88%E5%AF%86%E9%A1%BF%E5%9B%BE
    baidu之下,木有求总数的算法(实际上只能构造出特定的回路的样子)。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4969 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 03:56 · PVG 11:56 · LAX 19:56 · JFK 22:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.