Python

Question

我在一个二维数组上实现 BFS，列表作为 "queue"。我将当前单元格 (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是这个算法的起始坐标。我需要遍历整个地图来填充一些 'floor field' 来找到从地图的每个位置到这些目标的最短路径。 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

它没有遍历所有节点。

更新：

当我替换时它有效

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

和

visited = [[False for x in range(len(cells[0]))] for y in range(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

第二次通话时，您创建了单独的列表。所以当你改变一个时，值只改变了它。

Python - 多个 if 语句被忽略

Python - Multiple if statement get ignored

if-statement

multidimensional-array

breadth-first-search