Блог

Я совсем новичок в кодировании на Python и испытываю трудности с пониманием следующего кода ниже. Он основан на теории графов с использованием DFS для поиска наибольшей области среди всех областей островов. 1 представляет остров, а 0 представляет воду в сетке.

 def maxAreaOfIsland(grid):
    row, col = len(grid), len(grid[0])
    def dfs(i, j):
        if 0 <= i <= row - 1 and 0 <= j <= col - 1 and grid[i][j]:
            grid[i][j] = 0

#scans through all rows amp; cols and 
#turns number in the grid into 0 if all conditions are true?

            return  1   dfs(i - 1, j)   dfs(i   1, j)   dfs(i, j - 1)   dfs(i, j   1)
        return 0  

# recursive function that checks up, down, left, right in the grid. 
# when does it return 1?

    return max(dfs(i, j) for i in range(row) for j in range(col))

maxAreaOfIsland([[1,0,1,1,1],
                 [0,0,0,1,1],
                 [1,1,1,0,1]]) 
Out: 6
  

Я включил комментарии, которые отражают мое понимание до сих пор, но не уверен, что это правильно. Я совсем запутался со строки 4 и далее, особенно в рекурсивной части.
Может ли кто-нибудь объяснить подробно? Обычно такие коды, как правило, имеют очередь / удаление из очереди для записи того, посещался ли остров, но я не думаю, что в этом коде это есть?

Я думаю, вопрос действительно в понимании алгоритма, а не в Python. Предоставленный код Python довольно прост.

Код содержит функцию, maxAreaOfIsland которая, в свою очередь, содержит рекурсивную функцию dfs . Эти 2 функции образуют 2 уровня вычислений. Давайте рассмотрим эти слои отдельно.

 # outer layer
def maxAreaOfIsland(grid):
    row, col = len(grid), len(grid[0])
    # function dfs() definition
    return max(dfs(i, j) for i in range(row) for j in range(col))
  

Итак, внешний уровень очень прост — вычислите dfs(i, j) для всех возможных i , а j затем выберите максимальное вычисленное значение.

 # inner layer - slightly modified
def dfs(i, j):
    # recursive case
    if (0 <= i <= row - 1 and 0 <= j <= col - 1) and grid[i][j] == 1:
        grid[i][j] = 0  # this is how we remember visited cells since we don't count zeros
        # optional prints to look at the grid during computation
        # print(i, j)
        # print(*grid, sep='n', end='nn')
        count_current = 1
        count_neighbors = dfs(i - 1, j)   dfs(i   1, j)   dfs(i, j - 1)   dfs(i, j   1)
        return  count_current   count_neighbors
    # trivial case and out-of-borders case
    else:
        return 0
  

Внутренний слой немного сложнее. Что он делает? (1) Он получает i и j . (2) Если ячейка содержит 0 , то это тривиальный случай (вода) или мы вне сетки — просто верните 0 . (3) Если ячейка содержит 1 , то это рекурсивный регистр (land) — функция начинает подсчитывать количество всех 1 смежных с данной ячейкой с каждым 1 подсчитанным переходом в 0 , чтобы избежать двойного подсчета.

Ваш образец сетки содержит 3 строки (0, 1, 2) и 5 столбцов (0, 1, 2, 3, 4). Предположим, что мы находимся в i = 0, j = 2 . Это 1 . Мы подсчитываем его (текущий результат равен 1), превращаем его в 0 и смотрим на его соседей по очереди — верхний сосед находится вне сетки, нижний сосед — 0 , левый сосед — 0 , правый сосед — 1 . Мы не возвращаем текущий результат, а переходим к нужному соседу i = 0, j = 3 . Мы подсчитываем его (текущий результат равен 2), превращаем его в 0 и смотрим на соседей. Верхний сосед находится вне сетки, нижний сосед — 1 . Мы останавливаемся здесь, мы не возвращаем текущий результат, мы помним еще о 2 соседях, мы переходим к нижнему соседу i = 1, j = 3 . Мы подсчитываем его (текущий результат равен 3), превращаем его в 0 и смотрим на соседей. Верхний сосед 1 . Мы останавливаемся здесь, мы не возвращаем текущий результат, мы помним еще о 3 соседях, мы переходим к верхнему соседу i = 0, j = 3 . И так далее.

Мой совет — нарисовать простую примерную сетку (ручкой на листе бумаги) и вручную применить к ней алгоритм dfs.