从方阵合成边
从方阵合成边
提问于 2015-01-02 23:44:04
我发现了一些有趣的Project Euler问题(81-83)。它们都是“查找最短路径”在这个方阵中的变体。我将使用Djikstra的最短路径算法一次性解决所有这些问题。它们都有自己奇怪的变体，但都可以用不同的边缘设置建模(一些问题只能“向右和向下”移动，而另一些问题则是“向上/向下/向左/向右”。)
无论如何，我想我已经写了一种巧妙的方法来概括边的构造，使用一个“模式”列表来指定对于给定的节点，我可以为哪些相邻节点创建边。以下代码片段如下：
def makeGraph(fn="smallMatrix.txt", modes = [(0,1), (0,-1), (-1,0), (1,0)]):
for row in range(0, len(network)):
for col in range(0, len(network[row])):
#create edges
edgesFromNewNode = []
for mode in modes:
try:
#newEdge = ( edgeLength, (destination row, col) )
newEdge = ( network[row+mode[0]][col+mode[1]], ( row+mode[0] , col+mode[1] ) )
edgesFromNewNode.append(newEdge)
except IndexError:
pass
edgeCatalog[(row, col)] = edgesFromNewNode所以我不能理解为什么节点(0,0) (左上角节点)有四条边--它应该只有两条有效的边(1,0)和(0,1)。然后我意识到，当我将模式掩码应用到(0,0)时，我得到了像(0，-1)和(-1,0)这样的东西，它们不是索引错误--他们说使用列表的末尾。
在处理row=0或col=0时，我可以用一堆粗略的if-then-else用例来解决这个问题，但这太粗俗了。我希望有一种比这更具蟒蛇风格的方法。有什么建议吗？
Stack Overflow用户
发布于 2015-01-04 01:23:06
要明确。下面的变种并不比try... except IndexError:更长，也更清晰
if 0 <= row+mode[0] < len(network):
if 0 <= col+mode[1] < len(network[row]):
newEdge = (...)
edgesFromNewNode.append(newEdge)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27744644
复制相关文章
相似问题
腾讯云开发者
