python - 从方阵组成边

Question

我发现了几个有趣的欧拉计划问题 (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 案例来解决这个问题，但这太恶心了。我希望有比这更 pythonic 的方法。有什么建议么？

Answer 1

一般来说，网格大小为 m 行乘以 n 列，您可以从一个单元格移动到任何有效的相邻单元格。然后您可以使用方向数组 (类似于你的模式)

dx[4]={0,-1,0,1} // movement in rows
dy[4]={-1,0,1,0} // movement in columns

现在假设您在单元格 x,y 并且您想要转到它们有效的相邻单元格

 int valid(int i,int j)
 {
    if(i>=0&&i<m&&j>=0&&j<n)return 1;
    return 0;
 }

 for(i=0;i<4;i++)
 {
     new_x=dx[i]+x;
     new_y=dy[i]+y;
     if( valid(new_x,new_y) )
     {
         /* new_x,new_y is valid adjacent cell
            do whatever you want to process with it  */
     }
 } 

我想这样更干净。