Привет, ребята! Сегодня мы собираемся погрузиться в увлекательный мир подсчета островов в сетке. Независимо от того, являетесь ли вы новичком или опытным программистом, эта статья в блоге предоставит вам обзор различных методов решения этой проблемы. Итак, начнём!
Прежде всего, что мы подразумеваем под «островами» в сетке? Итак, представьте, что у вас есть 2D-сетка, состоящая из ячеек. Каждая ячейка может быть либо землей («1»), либо водой («0»). Остров — это группа связанных наземных ячеек, где связь может быть горизонтальной или вертикальной, но не диагональной. Наша задача — посчитать количество островов в заданной сетке.
Метод 1: поиск в глубину (DFS)
DFS — популярный метод обхода графов. В этом случае мы можем рассматривать сетку как граф, где каждая ячейка участка является узлом, а две соседние ячейки участка соединены ребром. Идея состоит в том, чтобы выполнить DFS для каждой непосещенной ячейки земли, отметив все ее подключенные ячейки земли как посещенные. Подсчитав количество вызовов DFS, мы можем определить количество островов.
def dfs(grid, row, col):
if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] != '1':
return
grid[row][col] = '0' # Mark cell as visited
# Perform DFS on adjacent cells
dfs(grid, row + 1, col)
dfs(grid, row - 1, col)
dfs(grid, row, col + 1)
dfs(grid, row, col - 1)
def count_islands(grid):
if not grid:
return 0
num_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
num_islands += 1
dfs(grid, i, j)
return num_islandsМетод 2: поиск в ширину (BFS)
Подобно DFS, BFS также можно использовать для подсчета островов в сетке. Ключевое отличие состоит в том, что BFS использует очередь для изучения соседей ячейки, а DFS использует рекурсию.
from collections import deque
def bfs(grid, row, col):
queue = deque([(row, col)])
grid[row][col] = '0' # Mark cell as visited
while queue:
row, col = queue.popleft()
# Explore adjacent cells
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_row, new_col = row + dx, col + dy
if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and grid[new_row][new_col] == '1':
queue.append((new_row, new_col))
grid[new_row][new_col] = '0' # Mark cell as visited
def count_islands(grid):
if not grid:
return 0
num_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
num_islands += 1
bfs(grid, i, j)
return num_islandsМетод 3: Алгоритм заливочного заполнения
Алгоритм заливочного заполнения — это еще один подход к решению этой проблемы. В его основе лежит концепция раскраски связных компонентов. Мы можем начать с любой ячейки суши и залить соседние ячейки земли другим цветом. Повторив этот процесс для всех непосещенных ячеек суши, мы сможем подсчитать количество островов.
def flood_fill(grid, row, col):
if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] != '1':
return
grid[row][col] = '0' # Mark cell as visited
# Flood fill adjacent cells
flood_fill(grid, row + 1, col)
flood_fill(grid, row - 1, col)
flood_fill(grid, row, col + 1)
flood_fill(grid, row, col - 1)
def count_islands(grid):
if not grid:
return 0
num_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
num_islands += 1
flood_fill(grid, i, j)
return num_islandsВот и все! Мы исследовали три различных метода подсчета островов в сетке: DFS, BFS и алгоритм заливки. Каждый метод имеет свои преимущества и может быть реализован с использованием различных языков программирования.
В заключение, подсчет островов в сетке — интересная задача, которую можно решить с помощью различных алгоритмов. Независимо от того, предпочитаете ли вы DFS, BFS или алгоритм заливки, эти подходы предоставляют эффективные способы решения этой задачи. Так что давайте, попробуйте и посмотрите, какой из них лучше всего подходит для вашего конкретного случая использования!