• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2488 – A Knight’s Journey【骑士游历】

    ACM-POJ EXP 235阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给出一个国际棋盘的大小,判断马能否不重复的走过所有格,并记录下其中按字典序排列的第一种路径。

    经典的“骑士游历”问题,DFS水题一道

    解题思路

    难度不大,但要注意的地方有3点:

    1、 题目要求以”lexicographically”方式输出,也就是字典序…要以字典序输出路径,那么搜索的方向(我的程序是path()函数)就要以特殊的顺序排列了…这样只要每次从dfs(A,1)开始搜索,第一个成功遍历的路径一定是以字典序排列…

    下图是搜索的次序,马的位置为当前位置,序号格为测试下一步的位置的测试先后顺序

    按这个顺序测试,那么第一次成功周游的顺序就是字典序

    2、国际象棋的棋盘,行为数字p;列为字母q

    3、网上有同学说 这道题最后一组数据后是有空行的会PE…,我测试过,不会的,能AC

    转载请注明:EXP 技术分享博客 » POJ2488 – A Knight’s Journey【骑士游历】

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址