CODEWITHSUNDEEP
pythonalgorithmgridflood-fill
elihar
elihar

Reputation: 109

Flood fill working only on squared matrix?

I'm trying to implement flood fill to find all available cells in a grid from which my robot can move to. if a cell is occupied its value will be 1, and if a cell is free its value will be 0. my code seems to work on squared matrices but not on other matrices. In my code I mark the reachable cells with the number 2.

Here is my code:

 def floodfill(matrix, x, y):

    if matrix[x][y] == 0:
        matrix[x][y] = 2

        if x > 0:
            floodfill(matrix,x-1,y)
        if x < len(matrix[y]) - 1:
            floodfill(matrix,x+1,y)
        if y > 0:
            floodfill(matrix,x,y-1)
        if y < len(matrix) - 1:
            floodfill(matrix,x,y+1)

This matrix seems to work:

def main():

    maze = [[0, 1, 1, 1, 1, 0, 0, 0, 1, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 0, 0],
            [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
            [0, 0, 0, 1, 1, 0, 1, 0, 1, 0]]

    floodfill(maze, 0,0)
    print(maze)

And this matrix does not (same matrix with last column removed):

def main():

    maze = [[0, 1, 1, 1, 1, 0, 0, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 0],
            [0, 1, 0, 0, 0, 0, 1, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1],
            [0, 1, 0, 1, 1, 0, 1, 0, 1],
            [0, 0, 0, 1, 1, 0, 1, 0, 1]]

    floodfill(maze, 0,0)
    print(maze)

Would appreciate your help. Thanks!

Upvotes: 0

Views: 157

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59174

When accessing elements in the matrix, the row index comes first (the matrix is an array of rows), followed by the column index (each row is an array of numbers).

You want matrix[y][x], not matrix[x][y].

Upvotes: 0

Sheldore
Sheldore

Reputation: 39052

Your first matrix works because it is a square matrix where the number of rows and the numbers of columns are equal = 10.

In your second case, your matrix is not a square matrix because you have 10 rows (x variable) but only 9 columns (y variable). Hence, when you do 

y < len(matrix) - 1

len(matrix) is 10 which means you are going up to y < 9. Otherwise, you will get "List Index Out of Range Error". To get the correct numbers, you should check against the length of your rows which gives you the number of columns. One way is to use the length of first row as len(matrix[0]).

Similarly, for the x you should use the corresponding number of rows which can be accessed using len(matrix) which is 10 in your case. So, you should use

if x < len(matrix) - 1

instead of if x < len(matrix[y]) - 1: as juvian also pointed it out in the comments.

Other way is to convert your list of lists to a NumPy array and use the shape command to get the corresponding number of rows and columns.

Upvotes: 1

Related Questions