Широта Первый Поиск подход

Question

Я пытаюсь изучить BFS и замечаю два паттерна: один находит все узлы, которые могут запускать BFS одновременно, а затем запускает BFS, другой находит первый узел, который может запускать BFS и запускает BFS. Я застрял с то же самое, не понимая около 2 недель. Я приведу здесь два примера, оба из кода leetcode: один - стены и ворота, а другой - гнилые апельсины, где неправильный подход не дает результатов. В задаче «Стены и ворота» я пересекаю все узлы, помещаю все узлы, которые запускают BFS, в очередь, а затем запускаю BFS. Я получаю желаемый результат.

Стены и ворота:

Вам дана двумерная сетка amxn, инициализированная этими тремя возможными значениями.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Заполните каждую пустую комнату Расстояние до ближайших ворот. Если невозможно добраться до ворот, они должны быть заполнены INF.

Пример:

Для двумерной сетки:

INF -1 0 INF INF INF INF - 1 INF -1 INF -1 0 -1 INF INF

После запуска вашей функции двумерная сетка должна иметь вид:

3 -1 0 1 2 2 1 -1 1 -1 2 - 1 0 -1 3 4

Мое решение:

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        if len(rooms)==0:
            return 0
        INF=2147483647
        list1=[]

        rows=len(rooms)
        columns=len(rooms[0])
        for row in range(rows):
            for column in range(columns):
                if rooms[row][column]==0:
                    list1.append([row,column])

        while len(list1)>0:
            row,column=list1.pop(0)

            if row-1>=0:
                    if rooms[row-1][column]==2147483647:
                        rooms[row-1][column]=rooms[row][column]+1

                        list1.append([row-1,column])

            if row+1<rows:
                    if rooms[row+1][column]==2147483647:
                        rooms[row+1][column]=rooms[row][column]+1

                        list1.append([row+1,column])


            if column-1>=0:
                    if rooms[row][column-1]==2147483647:
                        rooms[row][column-1]=rooms[row][column]+1
                        list1.append([row,column-1])


            if column+1<columns:
                    if rooms[row][column+1]==2147483647:
                        rooms[row][column+1]=rooms[row][column]+1
                        list1.append([row,column+1])



        return rooms

Та же проблема, если я найду первый узел, который может инициировать BFS, добавлю в очередь, а затем обработаю BFS, имеющую два списка, не удастся А пока другая проблема гниющих апельсинов работает. (Здесь порядок вставки в очередь, кажется, имеет значение. Как мы определяем, какой подход следовать?

Гниющие апельсины:

В данной сетке каждая ячейка может иметь одно из трех значений:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Каждую минуту любой оранжевый * fre sh, который примыкает (в четырех направлениях) к гнилому апельсину, становится гнилым.

Возвращает минимальное количество минут, которое должно пройти до тех пор, пока ячейка имеет оранжевый цвет fre sh. Если это невозможно, вместо этого верните -1. ​​

Пример 1:

Ввод: [[2,1,1], [1,1, 0], [0,1,1]] Выход: 4

Пример 2:

Вход: [[2,1,1], [0,1,1], [1 , 0,1]] Вывод: -1 Объяснение: оранжевый цвет в нижнем левом углу (строка 2, столбец 0) никогда не гниет, поскольку гниение происходит только в 4-х направлениях.

Пример 3:

Ввод: [[0,2]] Выход: 0 Объяснение: Поскольку на минуте 0 уже нет свободных sh апельсинов, ответ просто 0.

Примечание:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

Спасибо за вашу помощь.