Generalities
Since you are performing pretty much the same operation within each of your 4 ifs, you can simplify the code using an helper function to generate the 4 neighbours and apply the same operation to each of them. For better performances, this helper can be a generator:
def neighbours(x, y):
for dx in [-1, 1]:
yield x + dx, y
for dy in [-1, 1]:
yield x, y + dy
def floodfill(grid, x, y):
# Set the starting point to 0, 0 amount of moves needed
grid[x][y] = 0
# Set the starting number, the algorithm will search for this number to continue its flood
number = 0
while True:
found = False
for y in range(len(grid)):
for x in range(len(grid[0])):
# If 'number' is found, continue the flood from there
if grid[x][y] == number:
for dx, dy in neighbours(x, y):
if 0 <= dx < len(grid[0]) and 0 <= dy < len(grid) and grid[dx][dy] == -1:
grid[dx][dy] = number + 1
found = True
# Break loop if max amount of steps is needed
if found == False:
break
# Increment 'number', next loop the algorithm will continue from this point
number += 1
return grid
if __name__ == '__main__':
floodfill([
[-1 ,-1 , '*', '*'],
['*' ,-1 ,-1 , '*'],
['*' ,'*' ,-1 , '*'],
[-1 ,-1 ,-1 , -1],
], 0, 0)
Now, from there:
- I changed the way to handle the
grid variable and made it a parameter, it allows for better reusability;
floodfill now modifies a parameter in-place and returns it; this is unnecessary and we need to figure out wether returning a fresh list or modifying the parameter in-place is the best option;- You spend a lot of time iterating over the elements of the grid only to learn that you can't do anything with them (yet): if only you kept track of the previously modified coordinates so you can check only their neighbours…
- You compute
len(grid[0]) and len(grid) twice for each point that is not a wall, better store them in a variable.
- You use
x to access a row of the grid (ordinate) and y to access an element in that row (abscissa) but check that x is lower than the width and y is lower than the height: you should probably use grid[y][x] to avoid errors when the grid is not square.
- You don't check if the starting point is in a wall and blindly replace it with
0.
Data structure
I don't know your use case, so I don't know the need you may have for reusability of your initial grid (like trying floodfill on the same grid from different starting points), but:
- If you expect the grid you pass to the function to hold the result of the computation, you can modify it in place and, thus, not return it;
- If you expect the function to return the result of the computation, then you should not modify the input.
In any case, to get better type consistency in the output, I would expect walls to be None rather than a string. If you want pretty characters for your walls, write a function that will print them out of the output of this one.
Using None in the output also means using them in the input in case you chose to modify the list in-place.
Otherwise, if you chose to return a completely new list, you can change the input a bit, as the user does not have to be aware of the inner of you function. You can choose to accept a list of booleans where truthy values reprensent the path and falsey values represent walls. Note that, this wording also means that, albeit we would favor input such as:
[[True, True, False, False],
[False, True, True, False],
[False, False, True, False],
[True, True, True, True]]
your original grid (with walls marked as None) of
[[-1 ,-1 , None, None],
[None ,-1 ,-1 , None],
[None ,None ,-1 , None],
[-1 ,-1 ,-1 , -1]]
would work just the same, granted we use implicit boolean conversion.
Workload
We also need to keep track of modified values so we don't end up iterating over and over again over walls and values we already computed. Doing nothing but wasting time.
One solution is using a list/set of the current coordinates we need to take care of and a second one to store the coordinates we modify during the iteration of the first one. At the end of the iteration, we swap the two lists/sets and start over. Until there is no more coordinates added to the second one.
It works but feels a bit hackish. Instead, a better alternative is to use a FIFO queue: only one queue is used, we append elements to it as we modify them and we pop elements out of it one by one to take care of it (or its neighbours, actually). The FIFO queue guaranties that the poped element is always the oldest, so we are assured that the number associated to the coordinates of that element is less (or equal) than the number associated to the other elements of the queue.
You can use append() and pop(0) on a list as your FIFO queue, but it is not efficient, as pop(0) is \$O(n)\$. Instead, you should use append() and popleft() on a collections.deque
Proposed improvements
from collections import deque
def neighbours(x, y):
for dx in [-1, 1]:
yield x + dx, y
for dy in [-1, 1]:
yield x, y + dy
def floodfill(is_path, x, y):
height = len(is_path)
width = len(is_path[0])
grid = [[None] * width for _ in is_path]
if not is_path[y][x]:
# If we started in a wall, we can't reach anything
return grid
grid[y][x] = 0
modified = deque([(x, y)])
while modified:
x, y = modified.popleft()
number = grid[y][x]
for dx, dy in neighbours(x, y):
if 0 <= dx < width and 0 <= dy < height and is_path[dy][dx] and grid[dy][dx] is None:
grid[dy][dx] = number + 1
modified.append((x, y))
return grid
if __name__ == '__main__':
floodfill([
[True, True, False, False],
[False, True, True, False],
[False, False, True, False],
[True, True, True, True],
], 0, 0)
Note that if you want to use the version that modifies the parameter in-place, you just need to remove the grid building and return as well as and is_path[dx][dy] from the if; and changing the comparison back to grid[dy][dx] == -1.
