Заливка работает только на квадратной матрице?

Я пытаюсь реализовать заливку, чтобы найти все доступные ячейки в сетке, из которой мой робот может двигаться. если ячейка занята, ее значение будет равно 1, а если ячейка свободна, ее значение будет равно 0. Кажется, мой код работает с квадратными матрицами, но не с другими матрицами. В моем коде я помечаю доступные ячейки цифрой 2.

Вот мой код:

 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)

Эта матрица, кажется, работает:

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)

А эта матрица - нет (та же матрица с удаленным последним столбцом):

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)

Был бы признателен за вашу помощь. Спасибо!


python algorithm grid flood-fill
person elihar    schedule 20.12.2018    source источник
comment
Должно быть y ‹ len(matrix[0]) - 1 и x ‹ len(matrix) - 1   -  person juvian    schedule 20.12.2018

Ответы (2)


arrow_upward
1
arrow_downward

Ваша первая матрица работает, потому что это квадратная матрица, в которой количество строк и количество столбцов равны = 10.

Во втором случае ваша матрица не является квадратной матрицей, потому что у вас есть 10 строк (переменная x), но только 9 столбцов (переменная y). Следовательно, когда вы делаете

y < len(matrix) - 1

len(matrix) равно 10, что означает, что вы поднимаетесь до y < 9. В противном случае вы получите «Ошибка списка индексов вне диапазона». Чтобы получить правильные числа, вы должны сравнить длину ваших строк, которая дает вам количество столбцов. Один из способов — использовать длину первой строки как len(matrix[0]).

Точно так же для x вы должны использовать соответствующее количество строк, к которым можно получить доступ с помощью len(matrix), что в вашем случае равно 10. Итак, вы должны использовать

if x < len(matrix) - 1

вместо if x < len(matrix[y]) - 1:, поскольку juvian также указал это в комментариях.

Другой способ — преобразовать список списков в массив NumPy и использовать команду shape, чтобы получить соответствующее количество строк и столбцов.

person Sheldore    schedule 20.12.2018

arrow_upward
0
arrow_downward

При доступе к элементам матрицы сначала идет индекс строки (матрица представляет собой массив строк), за которым следует индекс столбца (каждая строка представляет собой массив чисел).

Вы хотите matrix[y][x], а не matrix[x][y].

person Matt Timmermans    schedule 20.12.2018