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

Question

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

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

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

11111  
10101  
10101  
11111  

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

11111  
10001  
10101  
11111

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

Возможны преимущества при использовании поиска в таблице и побитовых операций.

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