Подсчитайте количество "отверстий" в растровом изображении

Рассмотрим растровое изображение MxN, где ячейки равны 0 или 1. '1' означает заполнение, а "0" означает пустое.

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

Например, это имеет два отверстия:

... и это имеет только один:

Каков самый быстрый способ, когда M и N находятся между 1 и 8?

Разъяснение: диагонали не считаются смежными, имеют место только побочные проблемы.

Примечание. Я ищу что-то, что использует формат данных. Я знаю, как преобразовать это в график и [BD] FS, но это кажется излишним.

Ответ 1

Вам нужно сделать связанное обозначение компонентов на вашем изображении. Вы можете использовать двухпроходный алгоритм, описанный в статье я Википедии, приведенной выше. Учитывая небольшой размер вашей проблемы, может быть достаточно однопроходный алгоритм.

Вы также можете использовать BFS/DFS но я бы рекомендовал вышеупомянутые алгоритмы.

Ответ 2

Это похоже на приятное использование структуры данных с несвязанными наборами.
Преобразование растрового изображения в 2d-массив
петля через каждый элемент
если текущий элемент равен 0, объедините его с множеством из его "предыдущих" пустых соседей (уже посещенных)
если у него нет пустых соседей, добавьте его в свой собственный набор

то просто посчитайте количество наборов

Ответ 3

Могут быть преимущества, получаемые при использовании поиска таблиц и побитовых операций.

Например, целая строка из 8 пикселей может быть просмотрена в таблице 256 элементов, поэтому число отверстий в поле 1xN получается одним методом поиска. Тогда может быть какая-то таблица поиска из 256xK элементов, где K - это количество конфигураций отверстий в предыдущей строке, что соответствует количеству полных отверстий и конфигурации следующего отверстия. Это просто идея.