@vakavakvaka

Как найти все соседние клетки одинакового типа в двумерном массиве?

Всем привет!
Дан двумерный массив по типу этого:
6f0240550ed74fd8955ffb0433d2de15.png
Необходимо искать все соседние клетки одного цвета, например если пользователь выбирает клетку под номером 1 на рисунке, то алгоритм должен выбрать все клетки, обведенные черной рамкой, если 2, то все, обведенные желтой.
Подскажите, пожайлуйста, в какую сторону копать?
Спасибо!
  • Вопрос задан
  • 1286 просмотров
Пригласить эксперта
Ответы на вопрос 4
@alexxandr
you'll see in memory only 0xDEADFACE
модификация волнового алгоритма: через нужные клетки волна проходит и их выбирает, на ненужных - затухает
Ответ написан
Комментировать
DmitryITWorksMakarov
@DmitryITWorksMakarov
Представим, что двумерный массив - это граф, где каждая клетка - это узел. Данные узла: его координаты, цвет, массив ссылок на соседей, булево значение посещен/не посещен.

Отметить все узлы непосещенными.
На вход алгоритма подается узел графа.
Процедура P:
1. Выдать координаты входного узла.
2. Пометить входной узел посещенным.
3. Применить процедуру Р ко всем непосещенным соседям такого же цвета.

Необязательно строить граф явно. Можно соседей получать непосредственно в процедуре Р. Для "посещен/не посещен" нужна какая то быстрая и компактная структура данных, в которую можно быстро записать координаты клетки и быстро проверить: записывались ли раньше какие-либо координаты.
В простейшем случае - это булев двумерный массив того же размера, что и исходный. Но в зависимости от исходных данных и ограничений, другие способы могут быть более подходящими.
Ответ написан
@deliro
Агрессивное программирование
Вот так
Не знаю, знаком ли питон, но суть понять можно. Вся соль в методе find.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы