我有一個這樣的清單：
a=[
["x", "x", 0, 0, "x", "x"],
[ 0, 0, 0, 0, "x", "x"],
["x", "x", 0, 0, 0, "x"],
["x", "x", 0, 0, 0, 0 ]
]
Q1：
我希望串列中相互連接的任何 x 在一個組中
例子：
第 1 組 =
(0,0),(0,1)第 2 組 =
(0,4),(0,5),(1,4),(1,5),(2,5)第 3 組 =
(2,0),(2,1),(3,0),(3,1)
“解決辦法是什么？”
Q2：
我怎么知道兩組之間哪條路徑最短
uj5u.com熱心網友回復：
對于 Q1，您可以使用與坐標關聯的串列逐行和逐列瀏覽矩陣以形成組。將每個坐標放置在當前位置的上方或左側的連接位置串列中。沒有連接時創建一個新串列（組），當位置連接兩個不同組時合并串列。
a=[
["x", "x", 0, 0, "x","x"],
[ 0, 0, 0, 0, "x","x"],
["x", "x", 0, 0, 0, "x"],
["x", "x", 0, 0, 0, 0 ]
]
groups = dict() # group (list) at each coordinate
for r,row in enumerate(a):
for c,v in enumerate(row):
above = groups[r-1,c] if r and a[r-1][c] == v else None
left = groups[r,c-1] if c and a[r][c-1] == v else None
if above and left and above is not left:
above.extend(left) # merge left into above group
for rc in left: groups[rc] = above
g = above or left or [] # select existing group or new
g.append((r,c)) # add r,c to selected group
groups[r,c] = g # identify coordinate's group
# extract distinct groups from coordinate assignments
groups = list({id(g):g for g in groups.values()}.values())
輸出：
# all groups (i.e. groups of "x"s and groups of 0s)
print(groups)
[[(0, 1), (0, 0)],
[(1, 2), (3, 2), (1, 3), (3, 5), (3, 3), (0, 2),
(2, 4), (2, 3), (2, 2), (1, 0), (3, 4), (1, 1), (0, 3)],
[(1, 4), (1, 5), (0, 5), (0, 4), (2, 5)],
[(3, 0), (2, 0), (3, 1), (2, 1)]]
# only "x" groups
xGroups = [g for g in groups if a[g[0][0]][g[0][1]] == "x"]
print(xGroups)
[[(0, 1), (0, 0)],
[(1, 4), (1, 5), (0, 5), (0, 4), (2, 5)],
[(3, 0), (2, 0), (3, 1), (2, 1)]]
對于 Q2，您可以撰寫一個函式，通過擴展第一組的每個坐標可以通過的路徑到達第二組的任何坐標，同時僅通過 0 個位置（技術上是廣度 -第一次搜索）：
def distance(a,g1,g2):
rows = len(a)
cols = len(a[0])
distance = 1
seen = set(g1) # track visited coordinates
paths = g1 # current reach, starts with g1 coordinates
while paths:
nextPaths = set()
for r,c in paths:
for nr,nc in [(r,c-1),(r,c 1),(r-1,c),(r 1,c)]: #neighbours
if nr not in range(rows): continue
if nc not in range(cols): continue
if (nr,nc) in seen: continue # no doubleback
if (nr,nc) in g2: return distance # g2 reached
if a[nr][nc] == 0:
nextPaths.add((nr,nc)) # advance on 0s
seen.add((nr,nc))
distance = 1 # g2 not reached, need more steps
paths = nextPaths # start from positions reached so far
return None
print(distance(a,xGroups[0],xGroups[1])) # 3
print(distance(a,xGroups[1],xGroups[2])) # 4
print(distance(a,xGroups[0],xGroups[2])) # 2
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/351067.html