具有多个起点的洪水填充 BFS 算法（二维数组）

Question

我有一个用“.”填充的二维数组。或字母表中的字母（“A”、“B”、“C”、...）。现在假设我们只有“.”、“A”、“B”。我需要通过替换“.”来填充数组。使用“A”或“B”取决于哪个最接近特定的“。”，并且如果两个字母共享到“。”的最短路径那么我们需要将其保留为“。”

我的想法是从每个起始坐标（“.”）开始进行两次 BFS 搜索。第一次搜索找到到“A”的最小距离，第二次搜索找到到“B”的最小距离。如果路径相同，那么我将保留“.”。我将为每个具有“.”的坐标重复此操作。

我相信这会奏效，但似乎效率不高（尤其是当数组中有许多不同的字母时）。我想知道我是否缺少更好的方法来完成此任务？

（我正在使用 java 但语言无关紧要，我对算法感兴趣）

Answer 1

要实现平局算法，我的泛洪思路行不通。你原来的想法更好。但是，您不必为此执行 BFS。您可以只计算曼哈顿距离。

mymap = [
   '..........',
   '..B.......',
   '..........',
   '..........',
   '....C.....',
   '..........',
   '.......A..',
   '..........',
]

array = [list(row) for row in mymap]

def prt(array):
    for row in array:
        print( ''.join(row) )

roots = []
rootc = []
for y,row in enumerate(array):
    for x,char in enumerate(row):
        if char != '.':
            roots.append((x,y))
            rootc.append( char )

def mandist(a,b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

result = [list(row) for row in mymap]

for y,row in enumerate(array):
    for x,char in enumerate(row):
        if char != '.':
            continue
        dist = [mandist((x,y),root) for root in roots]
        # Find minimum distance.
        minx = min(dist)
        # If there is only one, mark the cell.
        if dist.count(minx) == 1:
            result[y][x] = rootc[dist.index(minx)]

prt(array)
print()
prt(result)

输出：

..........
..B.......
..........
..........
....C.....
..........
.......A..
..........

BBBBBBB...
BBBBBBB...
BBBBCCCAAA
BBBCCCCAAA
CCCCCCCAAA
CCCCCCAAAA
CCCCCAAAAA
CCCCCAAAAA

所以整个右上角都是平局。

具有多个起点的洪水填充 BFS 算法（二维数组）

flood fill BFS algorithm (2d array) with multiple starting points

arrays

breadth-first-search

flood-fill