Алгоритм Flood fill на Python

Алгоритм Flood fillopen in new window возвращает замкнутую область внутри массива. Кроме областей связанных с графикой, алгоритм может применяется для поиска замкнутых областей в игре Го и для сходных задач.

Алгоритм основан на рекурсии. Проверяется заданный элемент массива, затем процедура вызывается для всех соседних элементов:

Flood_fill(node)
  Если node не подходит по условиям то завершить функцию

  Обработать node

  Вызывать Flood_fill для всех соседних с node элементов

1
2
3
4
5
6

Реализация на Python:

F_SPACE = 0
F_WALL = 1

field = [
    [0, 1, 1, 1],
    [1, 0, 0, 0],
    [0, 0, 1, 1],
    [0, 1, 0, 0]
]

def flood_fill(field, x, y, w, h,  res):
    if x < 0 or y < 0 or x >= w or y >= h:
        return

    if field[y][x] == F_WALL:
        return

    if (x, y) in res:
        return

    res.add((x, y))

    flood_fill(field, x - 1, y, w, h, res)
    flood_fill(field, x + 1, y, w, h, res)
    flood_fill(field, x, y + 1, w, h, res)
    flood_fill(field, x, y - 1, w, h, res)

res = set()

res.clear()
flood_fill(field, 0, 0, 4, 4, res)
print(res) # {(0, 0)}

res.clear()
flood_fill(field, 1, 0, 4, 4, res)
print(res) # set()

res.clear()
flood_fill(field, 1, 1, 4, 4, res)
print(res) # {(1, 2), (3, 1), (2, 1), (1, 1), (0, 3), (0, 2)}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Алгоритм легко модифицируется для случая с трёхмерным массивом или если нужно учитывать соседние элементы по диагоналям.

# Алгоритм Flood fill на Python

Алгоритм Flood fill на Python