主题：求从一个棋盘的左上角走到右下脚共有几总走法？
zqnhlm
[专家分：780] 发布于 2005-08-09 19:55:00
求从一个棋盘的左上角走到右下脚共有几总走法？
长宽由用户输入，棋盘当中还有一些是障碍物是不能通过的，而且走的时候只能向右或者向下走，跟我说一下解题的思路跟方法就行了，谢谢！
回复列表 （共11个回复）
沙发
moz [专家分：37620] 发布于 2005-08-09 14:53:00
1. 把点做成数组,标记障碍物位置
2. 定当前位置,定可跳位置,
3. 可用递归,(就是说跳完某一步,回到上一步的位置重新计算下一步)
也可以用标记(与递归同样道理)
4. 到达终点计数,递归
板凳
shiyr [专家分：390] 发布于 2005-08-09 18:58:00
照你这么说应该有无穷组解,,, 因为你可以无限制的在两个块中自由来回
需要改动 有两种改动提醒
1.只许向右和下走
简单的动态规划...
2.任意方向,走过的地方就不能再走
这个 只能用递归了...
3 楼
zqnhlm [专家分：780] 发布于 2005-08-09 19:56:00
不好意思，忘加了，只能向右和向下！
4 楼
shiyr [专家分：390] 发布于 2005-08-09 20:19:00
那就是典型的动归方法了 或者用记忆化搜索..
O(n^2)的...
5 楼
jyf1987 [专家分：930] 发布于 2005-08-09 21:20:00
用2个循环嵌套
一个以坐标x为循环变量,里面那个以坐标y为循环变量
这样就只能向右或者向下了
然后分析判断,坐标处能不能走
建议地图用个2唯数组表示,有障碍物不能走.该处存储的数字为1,没有障碍的存储数字为0,好判断点
6 楼
zqnhlm [专家分：780] 发布于 2005-08-09 21:35:00
………………
劝你快点改改吧！
7 楼
moz [专家分：37620] 发布于 2005-08-10 11:22:00
劝谁改?
TO菱纸
不一定会无穷解的
定义两个数组
第一个数组储存标志: 障碍物标志 -1
已经走过的标志 +1
可跳位置 (未越界) and 0
第二个数组储存第几步的位置: 位置的表现可以用一维的顺序位置,
也可以用二维的下标位置.
跳到终点,计数,根据位置数组返回上一个位置跳另一个下一个位置
或者无路可走,根据位置数组返回上一个位置跳另一个下一个位置
往回走的时候需要把当前位置标志置0
只是这样会导致各种各样的迂回绕圈的路径,但这也是正确计算总路径的方法.
因为她之前没提向右下的方向要求.
因为我书本知识严重缺乏,理论知识知之甚少,所以很多术语表达都不懂,
表达能力不好,表达不清楚.
所以很有可能你们会看不懂我在说什么,请多多原谅.
8 楼
moz [专家分：37620] 发布于 2005-08-10 11:26:00
有一个马踏棋盘的题目
faintzw提的技术名称是深度搜索动态规划
(老实说,因为文化程度低的缘故,对高等技术我不在行)
9 楼
zqnhlm [专家分：780] 发布于 2005-08-10 15:33:00
TO七楼moz：
“因为她之前没提向右下的方向要求”
拜托我是男的不要用女字旁的“她”
10 楼
lushoufa [专家分：140] 发布于 2005-08-11 08:26:00
其实他也不是男的，[em19][em19][em19]
我来回复
您所在位置：