Как найти площадь соединенных островов (Python, теория графов) - PullRequest
Новая
       87

Как найти площадь соединенных островов (Python, теория графов)

0 голосов
/ 28 марта 2019

Привет. Я имею в виду проблему теории графов при поиске связанных островков. https://www.geeksforgeeks.org/find-the-number-of-islands-set-2-using-disjoint-set/ Это помогает найти количество подключенных островов.

У меня есть связанная проблема: Найдите область самых больших островов (1), включая воду (0), которая его окружает. Код для поиска связанных островов приведен ниже. Но я не знаю, как написать алгоритм поиска области ... 

def numIslands(graph):

    row = len(graph)
    col = len(graph[0])
    count += 1

    for i in range(row):
        for j in range(col):
            if graph[i][j] == 1:
                dfs(graph, row, col, i, j)
                count += 1
    return count

def dfs(graph, row, col, x, y):
    if graph[x][y] == 0:
        return

    graph[x][y] = 0

    if x != 0:
        dfs(graph, row, col, x-1, y)

    if x != rows - 1:
        dfs(graph, row, col, x+1, y)

    if y != 0:
        dfs(graph, row, col, x, y-1)

    if y != col-1:
        dfs(graph, row, col, x, y+1)

Примеры входов и выходов приведены ниже: 

1111 
0101
11110

Area: 10

101
010
101

Area: 1

11111
10011 
11111

Area: 15

1111111
1000001
1011101
1000001
1111111

Area 35

1111111
1000001
1011100
1000001
1111111

Area 19

Будем благодарны за любые предложения о том, как поступить!

...