Поиск соседей в программировании — это процесс поиска элементов, расположенных рядом с заданным элементом в структуре данных (например, матрице или графе). Этот подход применяется для анализа взаимосвязей между элементами, определения их свойств на основе окружения и выполнения различных алгоритмов (например, поиск пути, кластеризация, фильтрация данных).
В случае двумерной матрицы под соседями элемента обычно понимают элементы, которые находятся непосредственно по горизонтали, вертикали и/или диагонали относительно данного элемента. Например, для матрицы размера N×M, элемент с координатами (i,j) может иметь до 8 соседей (если считать диагонали).
Всесторонний поиск соседей в матрице может понадобиться в ряде задач:
Алгоритмы поиска пути (графы, лабиринты)
Алгоритмы заливки областей (например, заливка краской)
Обработка изображений
Игры на клеточных полях (например, "Сапёр")
Кластеризация данных
Моделирование физических процессов
Алгоритмы поиска кластеров (например, DBSCAN)
Обработка текста и символьных данных
Таким образом, всесторонний поиск соседей позволяет эффективно решать задачи, где требуется анализировать не только локальные данные в одной точке, но и её окружение.
Прежде чем мы продолжим, хочу пригласить в мой телеграмм канал Don Python, где я делюсь интересными особенностями языка, не очевидными фишками и решаю разные задачи.
Простейший пример
def get_neighbors(matrix, row, col):
rows = len(matrix)
cols = len(matrix[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
neighbors = []
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if 0 <= new_row < rows and 0 <= new_col < cols:
neighbors.append(matrix[new_row][new_col])
return neighbors
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
neighbors = get_neighbors(matrix, 1, 1)
print("Neighbors of element at (1,1):", neighbors)
# >>> Neighbors of element at (1,1): [2, 8, 4, 6, 1, 3, 7, 9]Объяснение
1. Начинаем с объявления функции get_neighbors с параметрами:
matrix - матрица, с которой предстоит работать
row - индекс строки
col - индекс колонки
2. Получаем размер матрицы rows × cols
3. Массив directions содержит все возможные направления для поиска соседей в двумерной матрице.
Каждый элемент этого массива представляет собой кортеж (пару чисел), где:
Первое число (
dx) отвечает за направление по строкам (по вертикали),
Второе число (
dy) отвечает за направление по столбцам (по горизонтали).
Эти пары используются для смещения от текущей позиции элемента в двумерной матрице.
Направление | Пара чисел | Описание |
|---|---|---|
Вверх | (-1, 0) | Смещение вверх на одну строку (координата строки уменьшается, столбец остаётся тем же). |
Вниз | (1, 0) | Смещение вниз на одну строку (координата строки увеличивается, столбец остаётся тем же). |
Влево | (0, -1) | Смещение влево на один столбец (строка остаётся той же, координата столбца уменьшается). |
Вправо | (0, 1) | Смещение вправо на один столбец (строка остаётся той же, координата столбца увеличивается). |
Вверх-влево | (-1, -1) | Диагональное смещение: вверх на одну строку и влево на один столбец. |
Вверх-вправо | (-1, 1) | Диагональное смещение: вверх на одну строку и вправо на один столбец. |
Вниз-влево | (1, -1) | Диагональное смещение: вниз на одну строку и влево на один столбец. |
Вниз-вправо | (1, 1) | Диагональное смещение: вниз на одну строку и вправо на один столбец. |
Если произвольно распечатать массив directions и наложить его на матрицу, можно получить следующую картину:
(-1, -1) (-1, 0) (-1, 1)
(0, -1) (i, j) (0, 1)
(1, -1) (1, 0) (1, 1)Здесь:
Центр (i,j) — это текущая позиция элемента.
Каждая пара чисел из массива
directionsуказывает на одну из клеток вокруг этого элемента.
4. Создаём массив neighbors. В будущем мы наполним его всеми найденными соседями.
5. И тут же возвращаем массив neighbors, опуская пока что основной алгоритм поиска.
Посмотрим что получается на текущий момент:
def get_neighbors(matrix, row, col):
rows = len(matrix)
cols = len(matrix[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
neighbors = []
return neighbors6. Теперь переходим к написанию алгоритма. Пробегаемся циклом for по массиву directions и распечатываем каждый кортеж в две переменные: dr, dc.
7. В первой строке цикла для каждого направления вычисляем новую позицию (строку и столбец) и проверяем, находятся ли они в пределах матрицы. Делаем мы это с помощью сложения индекса строки (row) со значением переменной dr и сложения индекса столбца (col) со значением переменной dc.
Процесс выглядит так:
Мы стоим на клетке (1,1) и хотим проверить соседей в разных направлениях.
Направление (−1,0) — движение вверх: новая позиция будет (0,1).
Направление (1,0) — движение вниз: новая позиция будет (2,1).
Направление (0,−1) — движение влево: новая позиция будет (1,0).
Направление (0,1) — движение вправо: новая позиция будет (1,2).
Если бы мы двигались по диагонали:
Направление (−1,−1) — новая позиция (0,0).
Направление (1,1) — новая позиция (2,2).
8. Теперь с помощью условия нужно определить, находится ли позиция, к которой мы хотим обратится в пределах матрицы. Для этого нужно убедиться, что значение new_row находится в диапазоне от 0 до len(matrix) и new_col в диапазоне от 0 до len(matrix[0]).
9. Если условие верно, то мы можем утверждать что позиция, к которой мы хотим обратиться доступна и является соседней для позиции, с которой мы начали поиск. Добавляем значение позиции в массив neighbors. Если условие не верно, переходим к следующей итерации.
Рабочая функция:
def get_neighbors(matrix, row, col):
rows = len(matrix)
cols = len(matrix[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
neighbors = []
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if 0 <= new_row < rows and 0 <= new_col < cols:
neighbors.append(matrix[new_row][new_col])
return neighbors10. Нам осталось создать произвольную матрицу, вызвать функцию, получить массив соседей и вывести результат:
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
neighbors = get_neighbors(matrix, 1, 1)
print("Neighbors of element at (1,1):", neighbors)Можно вернуться к основному блоку кода и вновь проанализировать все этапы.
Практический пример. Размытие картинки
Предлагаю на практике посмотреть, что можно сделать с помощью метода поиска соседей, а так же узнать, каким образом можно расширить радиус поиска.
Один из простых и практичных примеров использования поиска соседей в двумерном массиве — это фильтрация изображений. В этой задаче мы можем использовать алгоритм для обработки значений пикселей, чтобы, например, размыть изображение или применить детектор краев.
Введем некоторые ограничения для упрощения и наглядности примера:
Картинка не больше 256×256
Картинка должна быть черно-белой
Здесь не будет подробного разбора о том, как работает преобразование картинки в матрицу и обратно. Я просто размещу рабочий код
Я выбрал следующую картинку:
Процесс размытия состоит из 3х основных этапов:
Преобразование картинки в матрицу
Создание фильтра размытия
Преобразование матрицы обратно в картинку
Начальная структура файлов:
blur_img
img.jpg
main.pyПреобразование картинки в матрицу
Устанавливаем необходимую библиотеку:
pip install PillowИспользуем следующий код для создания функции преобразования:
from PIL import Image
def itm(*, image_path):
# Открываем изображение
img = Image.open(image_path)
# Преобразуем изображение в режим "L" (оттенки серого)
img = img.convert("L")
# Получаем размеры изображения
width, height = img.size
# Создаём матрицу
matrix = []
for y in range(height):
row = []
for x in range(width):
# Получаем значение пикселя
pixel_value = img.getpixel((x, y))
row.append(pixel_value)
matrix.append(row)
return matrixДалее мы будем использовать эту функцию как импортируемый модуль. Для этого изменим нашу структуру файлов:
blure_img
image_conversion
image_to_matrix.py
img.jpg
main.pyФункция размытия
В этом примере мы будем использовать матрицу, представляющую изображение, где каждое значение — это интенсивность пикселя (например, от 0 до 255 для серого изображения). Мы применим фильтр размытия, который заменяет значение каждого пикселя средним значением его соседей.
from image_conversion.image_to_matrix import itm
def apply_blur_filter(image):
rows = len(image)
cols = len(image[0])
blurred_image = [[0] * cols for _ in range(rows)]
directions = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 0), (0, 1),
(1, -1), (1, 0), (1, 1)]
for i in range(rows):
for j in range(cols):
pixel_sum = 0
count = 0
for dx, dy in directions:
new_x, new_y = i + dx, j + dy
if 0 <= new_x < rows and 0 <= new_y < cols:
pixel_sum += image[new_x][new_y]
count += 1
blurred_image[i][j] = pixel_sum // count
return blurred_image
matrix = itm(image_path="img.jpg")
blurred_image = apply_blur_filter(matrix)
Нам уже знакома эта функция, но в базовом примере мы находили соседей только для одного указанного элемента, а теперь нам нужно искать соседей для всех элементов матрицы. Для этого инициализируем два цикла, которые будут обрабатывать каждый пиксель картинки (элемент матрицы).
На уровне поиска соседей добавятся 3 новых строки:
pixel_sum- сумма значений всех соседних пикселейcount- количество соседей текущего пикселяblurred_image[i][j] = pixel_sum // count- расчет и присвоение нового значения
В итоге мы получаем новую матрицу с измененными значениями, которую нам нужно преобразовать в изображение.
Преобразование матрицы в картинку
Для сохранения матрицы обратно в изображение будем использовать установленную библиотеку Pillow. Процесс обратного преобразования включает создание нового изображения на основе матрицы пикселей и сохранение его в нужный формат.
from PIL import Image
def mti(matrix, output_path):
# Получаем размеры матрицы (высота и ширина изображения)
height = len(matrix)
width = len(matrix[0])
# Создаём новое изображение в режиме RGB
img = Image.new("L", (width, height))
# Заполняем изображение пикселями из матрицы
for y in range(height):
for x in range(width):
img.putpixel((x, y), matrix[y][x]) # Устанавливаем пиксель
# Сохраняем изображение
img.save(output_path)Обновленная файловая структура:
blure_img
image_conversion
image_to_matrix.py
matrix_to_image.py
img.jpg
main.pyИмпортируем функцию mti в main.py и вызываем с нужными параметрами в конце кода:
from image_conversion.image_to_matrix import itm
from image_conversion.matrix_to_img import mti
def apply_blur_filter(image):...
matrix = itm(image_path="img.jpg")
blurred_image = apply_blur_filter(matrix)
mti(matrix=blurred_image, output_path='blur_img.jpg')Исполняем файл main.py и получаем результат.
Было:
Стало:
Обновленная файловая структура:
blure_img
image_conversion
image_to_matrix.py
matrix_to_image.py
blur_img.jpg
img.jpg
main.pyПоиск соседей в произвольном радиусе
Предположим что предыдущего результата нам мало. Хочется регулировать степень размытия. Для этого недостаточно найти ближайших соседей. Требуется увеличить радиуса поиска.
Функции для получения матрицы из изображения и сохранения матрицы в виде изображения остаются без изменений. Нам нужно внести небольшие изменения в функцию apply_blur_filter.
Давайте посмотрим на изменения:
def apply_blur_filter(image, blur_radius=2):
rows = len(image)
cols = len(image[0])
blurred_image = [[0] * cols for _ in range(rows)]
offset_range = range(-blur_radius, blur_radius + 1)
for i in range(rows):
for j in range(cols):
pixel_sum = 0
count = 0
for dx in offset_range:
for dy in offset_range:
new_x, new_y = i + dx, j + dy
if 0 <= new_x < rows and 0 <= new_y < cols:
pixel_sum += image[new_x][new_y]
count += 1
blurred_image[i][j] = pixel_sum // count
return blurred_image
Объяснение
1. В параметрах функции добавляем новый аргумент blur_radius
2. Теперь вместо массива directions с координатами для поиска ближайших соседей, мы будем использовать диапазон от -blur_radius до blur_radius + 1. При blur_radius=2 по умолчанию диапазон будет таким: [-2, -1, 0, 1, 2]
3. Самым значительным изменением стало добавление четвёртого цикла. Теперь переменные dx и dy используются не в рамках одного цикла, где мы обходили соседние пиксели относительно текущего. Теперь dx представляет собой координату на оси x, относительно которой выполняется обход по оси y в диапазоне offset_range.
Предлагаю немного погрузиться в тонкости
Для каждого пикселя нам нужно рассчитать новое значение, которое будет средним по области blur_radius + (blur_radius + 1) x blur_radius + (blur_radius + 1), включающей этот пиксель. Если радиус размытия 2, то мы будем учитывать всех соседей в пределах 2 пикселей от текущего, то есть область 5x5.
Допустим, у нас есть следующая матрица значений яркости или цвета пикселей:
[
[10, 20, 30, 40, 50, 60],
[15, 25, 35, 45, 55, 65],
[20, 30, 40, 50, 60, 70],
[25, 35, 45, 55, 65, 75],
[30, 40, 50, 60, 70, 80],
[35, 45, 55, 65, 75, 85]
]Пусть координаты текущего пикселя будут (2, 2). Для пикселя с координатами (2,2) и значением 40, область размытия 5x5 включает следующие пиксели:
[
[10, 20, 30, 40, 50], # Соседи сверху
[15, 25, 35, 45, 55], # 2 строка
[20, 30, 40, 50, 60], # Строка с текущим пикселем (2,2)
[25, 35, 45, 55, 65], # 4 строка
[30, 40, 50, 60, 70] # Соседи снизу
]В данном случае ось x представлена строкой [20, 30, 40, 50, 60]. Учитывая диапазон поиска [-2, -1, 0, 1, 2], можно понять, что цикл for dx in offset_range обработает каждый пиксель в этой строке. На каждой итерации цикла for dx, цикл for dy in offset_range будет обрабатывать все значения по оси y в том же диапазоне [-2, -1, 0, 1, 2]. Таким образом, если на оси x текущая координата равна (-2, 0), что соответствует пикселю (2, 0) в матрице, то цикл for dy обработает все значения в столбце [10, 15, 20, 25, 30].
После применения размытия для каждого пикселя на основе его соседей, результирующая матрица может выглядеть примерно так:
[
[25, 30, 35, 40, 45, 50],
[30, 35, 40, 45, 50, 55],
[35, 40, 40, 45, 50, 60],
[40, 45, 45, 50, 55, 65],
[45, 50, 50, 55, 60, 70],
[50, 55, 60, 65, 70, 75]
]Алгоритм размытия с радиусом blur_radius = 2 усредняет значения для области 5x5 вокруг каждого пикселя. Пиксели на границах матрицы учитывают меньшее количество соседей (из-за того, что часть области выходит за границы изображения). В результате мы получаем "размытую" версию исходной матрицы, где каждый пиксель заменён на среднее значение его соседей.
Предлагаю оценить результат размытия с произвольным радиусом, где blur_radius=2:
Было:
Стало:
Итоги
К написанию статьи меня подтолкнула следующая задача - https://dmoj.ca/problem/coci13c2p2
Благодарю за прочтение, призываю к конструктивной критике и обсуждению в комментах.
Всем мир!
