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

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

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

Эти пары используются для смещения от текущей позиции элемента в двумерной матрице.

Если произвольно распечатать массив 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х основных этапов:

1. Преобразование картинки в матрицу

2. Создание фильтра размытия

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 пикселей от текущего, то есть область 5×5.

Допустим, у нас есть следующая матрица значений яркости или цвета пикселей:

[     [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, область размытия 5×5 включает следующие пиксели:

[     [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 усредняет значения для области 5×5 вокруг каждого пикселя. Пиксели на границах матрицы учитывают меньшее количество соседей (из-за того, что часть области выходит за границы изображения). В результате мы получаем «размытую» версию исходной матрицы, где каждый пиксель заменён на среднее значение его соседей.

Предлагаю оценить результат размытия с произвольным радиусом, где blur_radius=2:

Было:

Стало:

Итоги

К написанию статьи меня подтолкнула следующая задача — https://dmoj.ca/problem/coci13c2p2

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

Всем мир!