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

Question

[vakavakvaka]

Всем привет!
Дан двумерный массив по типу этого:

Необходимо искать все соседние клетки одного цвета, например если пользователь выбирает клетку под номером 1 на рисунке, то алгоритм должен выбрать все клетки, обведенные черной рамкой, если 2, то все, обведенные желтой.
Подскажите, пожайлуйста, в какую сторону копать?
Спасибо!

Comments

[vakavakvaka]

желтая цифра 1 на рисунке на самом деле 2 :-)

Answer 1

[Станислав Макаров]

Поиск в глубину

Comments

[LeEnot]

В глубину не подойдет, нужно в ширину

[Станислав Макаров]

LeEnot хм, а почему? Главное ж все связи покрыть? Или думаете будет медленнее?

[LeEnot]

Станислав Макаров: для поиска в глубину нужно будет сначала топологическую сортировку, потом еще серию поиска, а потом среди найденных компонент искать нужную. На небольшом поле разницы не будет, но сложнее в реализации

[Станислав Макаров]

LeEnot Зачем сортировку?) Поиск же не должен попасть никуда, кроме этой единственной компоненты, если начать его с выбранной клетки. я правда не пойму разницы)

[LeEnot]

Станислав Макаров: да наверн я не прав )

Answer 2

[alexxandr]

модификация волнового алгоритма: через нужные клетки волна проходит и их выбирает, на ненужных - затухает

Answer 3

[Дмитрий Макаров]

Представим, что двумерный массив - это граф, где каждая клетка - это узел. Данные узла: его координаты, цвет, массив ссылок на соседей, булево значение посещен/не посещен.

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

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

Comments

[LeEnot]

Задача поиска компонент связности серией обходов в ширину, вопрос как раз в способе хранения посещенных, но, думается мне, это нужно для какой-нибудь мобильной игры типа "Шарики" и поле небольшое, следовательно, булев массив вполне подойдет

[Дмитрий Макаров]

Вот и я об том же ^_^

Answer 4

[Roman K]

Вот так
Не знаю, знаком ли питон, но суть понять можно. Вся соль в методе find.