python求地图最短距离算法，大神们求指教
本帖最后由 zp307300084 于 2014-04-09 17:22 编辑假设这是一个地图，我要计算出走完这个地方的为0的最短距离
[
,
,
,
,
,
]
比如：'L' = 向左1步；'R' = 向右1步；'U' = 向上1步；'D' = 向下1步
最短距离则为：LLDRDR
这个没有出入口的，人可以随便放，只要走完全部标记为0的地方就行 地图是标准的2维数组，5*5、4*4、6*6依次类推 ，中间不会出现1,0,1,0,1断开的情况，线都是连着的 回复 1# zp307300084
第一, 能不能把你的 代码 放在 code 里. 这样, 格式不会变, 看得更清楚.
第二, 我没看懂你的答案, 不管人原来在哪里, 你的答案都走不出去. 另外, 你没说是 1 能走还是 0 能走.
第三, 我不一定能解答你的问题, 不过, 我对问题的结果很感兴趣. :em02: 至少说明入口在哪里，出口在哪里啊。。 感觉这是图论和拓扑学。。。
点有三种情况，我称为伯仲叔季，表示分别周围有4、3、2、1个1
这样定义：
伯：到了这个点后有三种选项，最复杂的点
0
0 0 0
0
仲：到了这个点后有两种选择
1
0 0 0
0
叔：到了这个点后没有选择,只能直走或转弯
1 0
0 0 0 0 0 1
1 1
季：起止点，到了这个点后就结束或者必须绕路（即成为一个新的起点）
1
1 0 1
0
所以就是，从季点作为起点，开始走，碰到仲点就成一个二叉，碰到伯点就成一个三叉，遍历所有可能，当长度超过最短长度（right_way_len)时，就continue，遍历上一个叉的另一种可能。直到遍历完所有可能。
想法是这样，编的话 得花点心思 可以考虑图算法里面的广度优先搜索，探索得到指定开始点和结束点之间的路径，那搜索到的就是你找到的路径。 五元组表示的是什么意思啊
页:
[1]