Подсчет островов в булевых матрицах

9

Учитывая булеву матрицу X , пусть 0 записей представляют море, а 1 запись представляет землю. Определите остров как вертикально или горизонтально (но не по диагонали) смежные 1 записи.N×мИкс011

Первоначальный вопрос заключался в подсчете количества островков в данной матрице. Автор описал рекурсивное решение ( памяти).О(Nм)

Но я безуспешно пытался найти потоковое (слева направо, а затем вниз к следующему ряду) решение, которое динамически подсчитывает острова с или O ( n ) или O ( n + m ) памятью (ограничений нет) за сложность времени). Это возможно? Если нет, то как я могу это доказать?О(м)О(N)О(N+м)


Несколько примеров ожидаемых выходов для определенных входов для countфункции:

соUNT(010111010)знак равно1;соUNT(101010101)знак равно5;соUNT(111101111)знак равно1;

соUNT(1111100100010110100011011111)знак равно2

соUNT(101111)знак равно1

PGS
источник
1
1. Что вы подразумеваете под «ортогональным»? Вы имеете в виду подключенный компонент? 2. Что мы можем предположить о том, как хранится матрица? Можем ли мы предположить, что он хранится во внешнем хранилище (например, на медленном жестком диске), поэтому вы можете читать любую часть, которую хотите, но будет быстрее читать ее блоком за раз? Или мы получаем матрицу в потоковом режиме, когда, получив немного входной матрицы, мы никогда не сможем увидеть этот входной бит снова?
DW
1
Хорошо, спасибо. Я призываю вас отредактировать вопрос, чтобы уточнить эти моменты. Если это потоковая передача, в каком порядке поступают биты матрицы? Сканирование слева направо среди ряда, затем вниз к следующему ряду?
DW
1
Пожалуйста, отредактируйте вопрос, чтобы включить все эти детали. Комментарии эфемерны.
Юваль
2
Не всю информацию, приведенную в комментариях, можно найти в самом посте. Часть этой информации довольно важна, например ваша потоковая модель. Комментарии могут исчезнуть, и поэтому (и в соответствии со стандартами сообщества) все необходимые детали должны стать частью основного сообщения.
Юваль
1
Какова сложность времени?
hengxin

Ответы:

4

Вот эскиз алгоритма, который одновременно хранит только две строки в памяти, поэтому памяти. Но так как вы можете запустить этот алгоритм для транспонирования матрицы без проблем, фактическая сложность составляет O ( min ( m , n ) ) памяти. Время обработки O ( m n ) .О(м)О(мин(м,N))О(мN)

  1. Инициализация. Просканируйте первую строку и найдите все связанные подстроки этой строки. Присвойте каждой непересекающейся подстроке уникальный положительный идентификатор и сохраните его как вектор, который равен нулю, где равен нулю, а уникальный положительный идентификатор в противном случае.Икс

  2. Для каждой оставшейся строки назначьте уникальные идентификаторы (никогда не назначайте предыдущие уникальные идентификаторы, убедитесь, что ваши идентификаторы строго увеличиваются) для подстрок в этой строке снова. Просмотрите предыдущую строку плюс текущую строку в виде матрицы размером на m , и всем связанным областям следует назначить их минимум. Например:2м

    010402220333300506607080009990010402220333300504402020003330

    Нет необходимости обновлять предыдущий ряд для корректности этого алгоритма, только текущий.

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

    Теперь вы можете отказаться от предыдущей строки и назначить текущую строку предыдущей строке и двигаться дальше.

  3. Икс

orlp
источник
6

О(N)О(NжурналN)Nзнак равномΩ(N)

Предположим, что Алиса содержит двоичный вектор а Боб содержит двоичный вектор y 1 , , y n , и они хотят знать, существует ли индекс i такой, что 0 , x n и y 1 , 0 , у 2 , 0 ,Икс1,...,ИксNY1,...,YNяИксязнак равноYязнак равно12×(2N-1)Икс1,0,Икс2,0,...,0,ИксNY1,0,Y2,0,...,0,YNΣяИксяΣя(Икся+Yя)яΩ(N)Ω(N)

О(N)О(журналN)О(N)

Юваль Фильмус
источник