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

I have a 2D array filled with either "." or letters of the alphabet ("A", "B", "C", ...). For now let's say we just have ".", "A", "B". I need to fill in the array by replacing the "." with either "A" or "B" depending on which is nearest that particular ".", and if two letters share the shortest path to a "." then we need to leave it as a "."

My thought is to do two BFS searches from every starting coordinate ("."). One search finds the minimum distance to "A", and the second search finds the minimum distance to "B". If the paths are the same then I'll keep the ".". And I will repeat this for every coordinate that has the ".".

I believe this will work, but it seems inefficient (especially when there are many different letters in the array). I was wondering if I'm missing a much better way of accomplishing this?

(I'm using java but the language doesn't matter, I'm interested in the algorithm)

CodePudding user response：

To implement the tie algorithm, my flood idea doesn't work. Your original idea is better. However, you don't have to do a BFS for this. You can just compute the Manhattan distance.

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)

Output:

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

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

So the whole upper right corner is a tie.