publicID123
V2EX  ›  问与答

一条回溯题,思路有了,调试通不过啊……

  •  
  •   publicID123 · Oct 24, 2014 via iPad · 3107 views
    This topic created in 4243 days ago, the information mentioned may be changed or developed.
    题目:
    描述

    棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

    棋盘用坐标表示,A点(0, 0)、B点(n, m)(n, m为不超过15的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

    输入

    一行四个数据,分别表示B点坐标和马的坐标。

    输出

    一个数据,表示所有的路径条数。

    样例输入

    6 6 3 3

    样例输出

    6

    思路:
    开一个二维数组表示所有点的情况,马可以达到的点飙为 false 。

    只要卒和开始给的点重合就计数。

    感觉思路没错,但是就是调试不对啊,求大牛帮看看代码到底错在哪里了。

    代码:
    8 replies    2014-10-25 20:58:50 +08:00
    z7059652
        1
    z7059652  
       Oct 24, 2014
    回溯法的回溯之处 你有吗?
    xjx0524
        2
    xjx0524  
       Oct 25, 2014 via Android
    卒的起点是0,0啊,你从马踩的位置搜干什么
    再说这题递推就行不用搜索啊
    stackpop
        3
    stackpop  
       Oct 25, 2014
    首先,把回溯法的概念搞清楚。

    其次,建议楼主学一下 DFS, BFS
    msg7086
        4
    msg7086  
       Oct 25, 2014
    我只指出其中一个错误。

    if(map[x][y]=false)
    msg7086
        5
    msg7086  
       Oct 25, 2014
    第二个错误你自己思考吧,不难。我已经调通了,应该是没有错的。

    $ ./horse
    6 6 3 3
    6
    $ ./horse
    10 10 4 4
    6802
    randomize
        6
    randomize  
       Oct 25, 2014 via iPad
    @msg7086
    感谢。Accepted .

    剩余的一处错误是马自己的位置也是不能走的,而不仅仅是它能到的位置。

    另外,顺带问下大大……我这么写算什么?真的不是传说中的回溯么……
    randomize
        7
    randomize  
       Oct 25, 2014 via iPad
    似乎暴露了用了一下 publicID 233333333333
    msg7086
        8
    msg7086  
       Oct 25, 2014
    @randomize 应该是可以算作回溯DFS递归。
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   1011 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 23:07 · PVG 07:07 · LAX 16:07 · JFK 19:07
    ♥ Do have faith in what you're doing.