Python - 多个if语句被忽略

Question

我正在 2D 数组上实现 BFS，其中列表充当“队列”。我将当前单元格(i，j)的每个未访问的邻居添加到队列中，并在每个循环中弹出队列的头部作为当前单元格，直到队列为空。标准的东西。

问题似乎是每个循环中只执行一个“if”语句。我不明白为什么会发生这种情况。

for tgroup in targets.keys(): #group of targets
    for t in targets[tgroup]: #each target in group
        visited = [[False]*len(cells[0])]*len(cells)
        queue = []
        cur = None
        queue.append(t)
        visited[t[0]][t[1]] = True
        cells[t[0]][t[1]].fields[tgroup-3] = 0
        while len(queue) > 0:
            cur = queue[0]
            queue = queue[1:]

            if cur[0] > 0 and visited[cur[0]-1][cur[1]] is False:
                queue.append((cur[0]-1,cur[1]))
                visited[cur[0]-1][cur[1]] = True
                cells[cur[0]-1][cur[1]].fields[tgroup-3] = min(cells[cur[0]-1][cur[1]].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 't', cur

            if cur[0] < len(cells)-1 and visited[cur[0]+1][cur[1]] is False:
                queue.append((cur[0]+1,cur[1]))
                visited[cur[0]+1][cur[1]] = True
                cells[cur[0]+1][cur[1]].fields[tgroup-3] = min(cells[cur[0]+1][cur[1]].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'b', cur

            if cur[1] > 0 and visited[cur[0]][cur[1]-1] is False:
                queue.append((cur[0],cur[1]-1))
                visited[cur[0]][cur[1]-1] = True
                cells[cur[0]][cur[1]-1].fields[tgroup-3] = min(cells[cur[0]][cur[1]-1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'l', cur

            if cur[1] < len(cells[0])-1 and visited[cur[0]][cur[1]+1] is False:
                queue.append((cur[0],cur[1]+1))
                visited[cur[0]][cur[1]+1] = True
                cells[cur[0]][cur[1]+1].fields[tgroup-3] = min(cells[cur[0]][cur[1]+1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'r', cur

            if cur[0] > 0 and cur[1] > 0 and visited[cur[0]-1][cur[1]-1] is False:
                queue.append((cur[0]-1,cur[1]-1))
                visited[cur[0]-1][cur[1]-1] = True
                cells[cur[0]-1][cur[1]-1].fields[tgroup-3] = min(cells[cur[0]-1][cur[1]-1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'tl', cur

            if cur[0] > 0 and cur[1] < len(cells[0])-1 and visited[cur[0]-1][cur[1]+1] is False:
                queue.append((cur[0]-1,cur[1]+1))
                visited[cur[0]-1][cur[1]+1] = True
                cells[cur[0]-1][cur[1]+1].fields[tgroup-3] = min(cells[cur[0]-1][cur[1]+1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'tr', cur

            if cur[0] < len(cells)-1 and cur[1] > 0 and visited[cur[0]+1][cur[1]-1] is False:
                queue.append((cur[0]+1,cur[1]-1))
                visited[cur[0]+1][cur[1]-1] = True
                cells[cur[0]+1][cur[1]-1].fields[tgroup-3] = min(cells[cur[0]+1][cur[1]-1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'bl', cur

            if cur[0] < len(cells)-1 and cur[1] < len(cells[0])-1 and visited[cur[0]+1][cur[1]+1] is False:
                queue.append((cur[0]+1,cur[1]+1))
                visited[cur[0]+1][cur[1]+1] = True
                cells[cur[0]+1][cur[1]+1].fields[tgroup-3] = min(cells[cur[0]+1][cur[1]+1].fields[tgroup-3], cells[cur[0]][cur[1]].fields[tgroup-3]+1)
                print 'br', cur

targets 是该算法的起始坐标。我需要遍历整个 map 来填写一些“地板字段”，以找到从 map 的每个位置到这些目标的最短路径。 target 中的每个 t 都存储为元组 (i,j)

visited 是已访问节点的标记。

cur 是当前节点，存储为元组(i,j)。

cells 是二维数组。每个单元格都有一个列表属性.fields，其中包含每个目标的“floor field”权重，表示从该单元格到目标的距离。为了简单起见，目前非目标单元格的权重默认为 9。目标的权重默认为 0。

这是一个 9*9 输入映射示例:

4 1 1 1 1 1 1 1 1
0 1 1 0 0 0 0 1 0
0 1 1 1 1 2 0 1 0
0 1 1 1 1 2 0 1 0
0 1 1 0 0 0 0 1 0
3 1 1 0 0 0 1 1 0
3 1 1 0 0 0 1 1 0
0 1 1 0 0 0 1 0 0
0 5 5 5 0 0 1 0 0

但是为表示为数字3的目标生成的楼层字段是:

9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9

它不会遍历所有节点。

更新:

更换后就可以了

访问过 = [[False]*len(cells[0])]*len(cells)

与

visited = [[对于范围内的 x (len(cells[0])) 为 False] 对于范围内的 y(len(cells))]

谁能解释一下其中的区别吗？非常感谢!

Answer 1

第一次通话后

visited = [[False]*len(cells[0])]*len(cells)

visited 包含 len(cells) 个本质上相同的列表(它们都引用一个列表)。因此，当您更改其中的值时，所有这些值都会发生变化，因为它们是相同的。

>>>a = [[False]*4]*4
>>>a[0][0] = True
>>>a
>>>[[True, False, False, False],
   [True, False, False, False],
   [True, False, False, False],
   [True, False, False, False]]

>>> for x in a: print id(x)
>>> 135345096
    135345096
    135345096
    135345096

在第二次通话时，您创建单独的列表。因此，当您更改其中之一时，仅更改其中的值。