Заливка поля
Заливка закрашивает область: клетку, ее соседей того же цвета, их соседей и так далее. Рекурсия делает это коротко: закрасить клетку и вызвать заливку для четырех соседей.
Функция ничего не делает, если клетка за краем поля или не та, которую заливают. Закрашенная клетка меняет символ, поэтому во второй раз заливка в нее не войдет.
grid = [list("..#"), list(".##"), list("#..")]
n, m = 3, 3
def fill(i, j):
if 0 <= i < n and 0 <= j < m and grid[i][j] == ".":
grid[i][j] = "~"
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
fill(i + di, j + dj)
fill(0, 0)
for row in grid:
print("".join(row))
Остров — область из клеток «#», соседних по сторонам. Чтобы посчитать острова, перебирают все клетки поля. Встретив «#», запускают заливку: она стирает весь остров, а счетчик растет на один.
Пусть заливка возвращает размер острова, а на «.» — 0. Тогда ненулевой ответ значит «нашли новый остров», а сам ответ — его размер.
grid = [list("#.#"), list("#.."), list("..#")]
def sink(i, j):
if 0 <= i < 3 and 0 <= j < 3 and grid[i][j] == "#":
grid[i][j] = "."
return 1 + sink(i + 1, j) + sink(i - 1, j) + sink(i, j + 1) + sink(i, j - 1)
return 0
for i in range(3):
for j in range(3):
found = sink(i, j)
if found > 0:
print("остров из", found, "клеток")
Итог урока. Заливка закрашивает клетку и вызывает себя для соседей. Она выходит сразу, если клетка за краем поля или уже не подходит, а закрашенная клетка второй раз не обходится.
Заливка, которая возвращает размер, считает области и острова, а заливка с or отвечает, можно ли дойти от одной клетки до другой.
В последнем уроке главы — практика: Ханойская башня, скобки, разбиения числа и пути по полю.
Урок пройден
Заливка поля
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Заливка поля
Заливка поля рекурсией в Python: закрасить клетку и вызвать заливку для соседей, размер области, острова, путь в лабиринте. В 6 заданиях вы зальете область, найдете ее размер, посчитаете острова, найдете самый большой остров, пройдете лабиринт и прочитаете программу: что она выведет?