主题：[讨论]骑士游历问题
cmy28
[专家分：380] 发布于 2007-07-15 19:53:00
在n*n的国际象棋棋盘的某一位置(p,q)有一个马，用“马走日字”的规则，要求它不重复地走完所有格子。
输入：
n p q
输出：
一个n*n的矩阵，表示每个格子是第几个走到。
请问，这道大家很熟悉的题目除了回溯还有别的方法吗？
如有，最好有程序。谢谢！[em1][em1]
回复列表 （共8个回复）
沙发
cmy28 [专家分：380] 发布于 2007-07-30 18:27:00
有人来么？？
5555```````````````
帮助别人也是提高自己啊！！
板凳
suturkey [专家分：0] 发布于 2007-08-01 15:16:00
动规！！！！！
3 楼
cmy28 [专家分：380] 发布于 2007-08-01 16:24:00
请说明白点，怎么做？谢谢！
4 楼
vcacm [专家分：1500] 发布于 2007-09-23 20:37:00
归纳法。。。。
可以找规律的。。。。
也可以搜索。。。
具体代码GG上有。。
5 楼
wxfred [专家分：0] 发布于 2007-11-02 09:20:00
可以用近似广搜的算法：图标记法
先将起始点标记为0，其他点标记为-1；
接着在整个图中搜索标记为0的点；
然后以这个点为中心，将它能一步走到的点标记为1；
接着又在整个图中搜索标记为1的点；
然后以这个点为中心，将它能一步走到的点标记为2；
……
举例：
5*5的棋盘，起点为（1，1）
第一步：标记A[1，1]的值为0；其余的点标记为-1；
第二步：搜索整个图，找出值为0的点为（1，1）；
第三步：IF A[2，3]：=-1 THEN A[2，3]：=A[1，I]+1；IF语句是判断这个点是否走过
IF A[3，2]：=-1 THEN A[3，2]：=A[1，1]+1；
第四步：搜索整个图，找出值为1的点为（2，3）（3，2）；
第五步：……
……
图标记法（我这么称的，不知真名是什么）
还适用于“超级龙骑”
你可以用用。
6 楼
wxfred [专家分：0] 发布于 2007-11-04 16:42:00
对不起
你的题怎么不和我的一样
题目是一样的啊
但我的是求一点到另一点的最小步数,可以用动态规划求
7 楼
编程小菜菜 [专家分：90] 发布于 2007-12-06 21:04:00
我只知道回溯...
8 楼
散云霏霏 [专家分：10] 发布于 2008-02-24 13:59:00
应该是用回溯递归来求解吧，现在学了递归我觉得什么题都能用递归！
我来回复
您所在位置：