python求地图最短距离算法，大神们求指教

zp307300084

假设这是一个地图，我要计算出走完这个地方的为0的最短距离
[
[1,1,1,1,1],
[1,0,0,0,1],
[1,0,0,1,1],
[1,1,0,0,1],
[1,1,1,1,1],
]

比如：'L' = 向左1步；'R' = 向右1步；'U' = 向上1步；'D' = 向下1步

最短距离则为：LLDRDR

这个没有出入口的，人可以随便放，只要走完全部标记为0的地方就行

zp307300084

地图是标准的2维数组，5*5、4*4、6*6依次类推 ，中间不会出现1,0,1,0,1断开的情况，线都是连着的

q1208c

回复 1# zp307300084


第一, 能不能把你的 代码 放在 code 里. 这样, 格式不会变, 看得更清楚.

第二, 我没看懂你的答案, 不管人原来在哪里, 你的答案都走不出去. 另外, 你没说是 1 能走还是 0 能走.


第三, 我不一定能解答你的问题, 不过, 我对问题的结果很感兴趣.

XINBADA426

至少说明入口在哪里，出口在哪里啊。。

太平洋上的我

感觉这是图论和拓扑学。。。
点有三种情况，我称为伯仲叔季，表示分别周围有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，遍历上一个叉的另一种可能。直到遍历完所有可能。

想法是这样，编的话 得花点心思

icymirror

可以考虑图算法里面的广度优先搜索，探索得到指定开始点和结束点之间的路径，那搜索到的就是你找到的路径。

古龙想的回忆

五元组表示的是什么意思啊