Выделение подмножеств из двумерного массива

Рейтинг: 2Ответов: 2Опубликовано: 10.12.2014

Упрощенно: Есть массив

[[0,0,0,0,0],
 [0,1,1,0,0],
 [1,1,0,0,1],
 [0,1,0,0,1],
 [0,0,0,0,0]]

Как записать замкнутые области, состоящие из единиц в отдельные массивы? Как вариант

[[0,1,1],
 [1,1,0],
 [0,1,0]]

[[1],
 [1]]

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

php алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Интересная задача, не сталкивался пока. Вот похожая – сосчитать такие острова: Islands in a two dimensional array

А ещё вспомнилось правило обхода лабиринта - правой рукой всегда касаться стены. Можно не считать 1, а «идти» по нулям, касаясь правой рукой 1. Когда маршрут замкнулся — обошли остров. После этого остров сохранить, островные 1 в исходном массиве обнулить. Правда, может подвести, если в острове дырка, а в ней ещё один изолированный суб-остров : )

▲ 2

По ссылке, приведённой @Sergiks, используется рекурсивный алгоритм поиска в глубину. Если в PHP есть проблемы с глубиной рекурсии, можно сделать то же самое поиском в ширину. Обычно этот алгоритм используют для поиска пути, но он также может использоваться для определения элементов, принадлежащих одной связанной области. Достаточно запустить поиск в любой точке острова, и в момент, когда очередь опустеет, алгоритм пометит как посещённые все клетки, принадлежащие острову.