Поиск соседей в двумерном массиве / Хабр

Поиск соседей в программировании — это процесс поиска элементов, расположенных рядом с заданным элементом в структуре данных (например, матрице или графе). Этот подход применяется для анализа взаимосвязей между элементами, определения их свойств на основе окружения и выполнения различных алгоритмов (например, поиск пути, кластеризация, фильтрация данных).

В случае двумерной матрицы под соседями элемента обычно понимают элементы, которые находятся непосредственно по горизонтали, вертикали и/или диагонали относительно данного элемента. Например, для матрицы размера 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 neighbors

6. Теперь переходим к написанию алгоритма. Пробегаемся циклом 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 neighbors

10. Нам осталось создать произвольную матрицу, вызвать функцию, получить массив соседей и вывести результат:

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

Благодарю за прочтение, призываю к конструктивной критике и обсуждению в комментах.

Всем мир!

Поиск соседей в двумерном массиве