flood填充多起点BFS算法(2d数组)

Question

我有一个2D数组，里面有"。"或字母("A"， "B"， "C"，…)。现在我们假设我们只有" "， "A"， "我需要通过替换"。"与"A"或";B"取决于哪个最接近那个特定的";;，以及两个字母是否共享到";;然后我们需要将其保留为" ">

我的想法是从每个起始坐标(".")进行两次BFS搜索。第一次搜索找到到&;a &;的最小距离，第二次搜索找到到&;b&&;的最小距离。如果路径相同，我就保留"。我将对每一个带有" "的坐标重复此操作

我相信这将工作，但它似乎效率低下(特别是当数组中有许多不同的字母时)。我想知道我是否错过了一个更好的方法来完成这个?

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

Answer 1

要实现tie算法，我的flood想法不起作用。你原来的想法更好。然而，你不必为此做一个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

所以整个右上角是平直的