c++ 马走日问题

梦亦难书

c++没学好，在线求大神解答！！！        辛苦大神了  

1）问题描述
马从（0，0）出发，只能往右（右上或右下）跳，从（0，0）点到（8，4）点，这个区域内有多少种不同的路径，并打印出各种路径。
2）问题分析
这个问题可以从广义上来说是一个搜索问题，可以采用回溯的思想来解决，具体到编程时回溯往往是递归的形式，然而递归容易造成栈溢出，所以需要我们采用一定的措施防止栈溢出。
按照人的一般思维，假想当我们目前处在（0，0）点的时候，按照规则，我们可以走到（2，1）这个点和（1，2）这个点，
当我们选择走到（2，1）这个点的时候，我们下一步可以走到（4，0）、（1，2）或（3，3）这三个点，也就是说我们有三种选择；当我们选择走到（1，2）这个点的时候，我们下一步可以走到（2，0）、（3，1）、（3，3）或（2，4）这个点；依次类推，当点比较少的时候我们人脑还能承受，但当目标点距离我们的初始点比较远时，显然我们的大脑往往会很糊涂。
3）步骤
（1）针对题目中的坐标点，我们设计一个Point类来描述我们当前所处的状态，记录其横坐标和纵坐标。
（2）要打印出一条路径，就需要一个动态数组来记录走过的点，采用STL中的vector可以实现，对应程序中的path，其类型为vecetor<Point>。
（3）要记录下所有的路径，我们需要一个记录“一个完整的路径”的动态数组，对应程序中的ret，类型为vector<vector<Point>>。
（4）针对当前我们所处的状态，我们可以根据题目中的规则扩展出下一步可以到达的状态节点（注意不要越界），即选择列表，对应程序中的ls，类型当然是vector<Point>。
（5）当我们从当前节点做出“选择”（即下一步对应的那个点，记为ST）之后，需要将该“选择”从选择列表中移除，并将该“选择”添加到路径当中去，接着继续按照规则扩展节点做“选择”，直至到达目标节点；然后需要ST重新添加回选择列表中。

soupman

我觉得可以用队列，进行BFS,知道原理不会写

梦亦难书

soupman 发表于 2020-6-3 21:04
我觉得可以用队列，进行BFS,知道原理不会写

我没认真学，现在很无奈