Menghitung pulau dalam matriks Boolean

Diberi Boolean matrix , misalkan 0 entri mewakili laut dan 1 entri mewakili tanah. Mendefinisikan sebuah pulau sebagai vertikal atau horizontal (tetapi tidak diagonal) yang berdekatan 1 entri.$n \times m$$\mathrm X$$0$$1$$1$

Pertanyaan aslinya adalah untuk menghitung jumlah pulau dalam matriks yang diberikan. Penulis menggambarkan solusi rekursif ( $\mathcal{O}(nm)$ memori).

Tetapi saya gagal mencoba menemukan solusi streaming (kiri ke kanan, dan kemudian ke baris berikutnya) yang menghitung pulau secara dinamis dengan $\mathcal{O}(m)$ atau $\mathcal{O}(n)$ atau $\mathcal{O}(n+m)$ memori (tidak ada batasan untuk kompleksitas waktu). Apakah itu mungkin? Jika tidak, bagaimana saya bisa membuktikannya?

Beberapa contoh output yang diharapkan untuk input tertentu untuk countfungsi:

$count\begin{pmatrix} 010\\ 111\\ 010\\ \end{pmatrix} = 1; % count\begin{pmatrix} 101\\ 010\\ 101\\ \end{pmatrix} = 5; % count\begin{pmatrix} 111\\ 101\\ 111\\ \end{pmatrix} = 1;$

$count\begin{pmatrix} 1111100\\ 1000101\\ 1010001\\ 1011111\\ \end{pmatrix} = 2$

$count\begin{pmatrix} 101\\ 111\\ \end{pmatrix} = 1$

Berikut ini sketsa algoritma yang hanya menyimpan dua baris memori sekaligus, jadi memori. Tetapi karena Anda dapat menjalankan algoritma ini pada transpos matriks tanpa masalah, kompleksitas sebenarnya adalah memori . Waktu pemrosesan adalah .$O(m)$$O(\min(m, n))$$O(mn)$

1. Inisialisasi. Pindai baris pertama dan temukan semua substring yang terhubung dari baris itu. Tetapkan setiap pemisahan substring id positif unik dan simpan ini sebagai vektor yang nol di mana adalah nol dan sebaliknya, id positif unik.$X$

2. Untuk setiap baris yang tersisa menetapkan id unik (jangan pernah menetapkan ulang id unik sebelumnya, pastikan id Anda benar-benar meningkat) ke substring di baris itu lagi. Lihat baris sebelumnya ditambah baris saat ini sebagai matriks x , dan setiap area yang terhubung harus ditugaskan ke minimum. Sebagai contoh:$2$$m$

   $$\begin{array}0010402220333300\\ 506607080009990\end{array} \rightarrow \begin{array}0010402220333300\\ 504402020003330\end{array}$$

   Tidak perlu memperbarui baris sebelumnya untuk kebenaran dari algoritma ini, hanya yang saat ini.

   Setelah itu selesai, cari set semua id di baris sebelumnya yang tidak terhubung ke baris berikutnya, buang duplikat . Tambahkan ukuran set ini ke counter pulau Anda.

   Anda sekarang dapat membuang baris sebelumnya dan menetapkan baris saat ini ke baris sebelumnya dan melanjutkan.

3. Untuk menangani dengan benar baris terakhir, berpura-pura ada satu baris lagi nol di bagian bawah dan jalankan langkah 2 lagi.$X$

Orlp memberikan solusi menggunakan kata-kata ruang, yang merupakan bit ruang (dengan asumsi untuk kesederhanaan bahwa ). Sebaliknya, mudah untuk menunjukkan bahwa bit ruang diperlukan dengan mengurangi keterikatan pada masalah Anda.$O(n)$$O(n\log n)$$n=m$$\Omega(n)$

Misalkan Alice memegang vektor biner dan Bob memegang vektor biner , dan mereka ingin tahu apakah ada indeks sedemikian rupa sehingga . Mereka menjalankan algoritme Anda untuk matriks yang barisnya dan . Setelah baris pertama dibaca, Alice mengirimkan Bob serta konten memori, sehingga Bob dapat menyelesaikan algoritme dan membandingkan dengan jumlah komponen yang terhubung. Jika kedua angka cocok, kedua vektor tersebut terpisah (tidak ada indeks$x_1,\ldots,x_n$$y_1,\ldots,y_n$$i$$x_i=y_i=1$$2\times(2n-1)$$x_1,0,x_2,0,\ldots,0,x_n$$y_1,0,y_2,0,\ldots,0,y_n$$\sum_i x_i$$\sum_i (x_i+y_i)$$i$), dan sebaliknya. Karena protokol apa pun untuk set disjointness membutuhkan bit (bahkan jika itu bisa keliru dengan probabilitas konstan kecil), kami menyimpulkan batas bawah , yang berlaku bahkan untuk protokol acak yang diizinkan untuk melakukan kesalahan dengan beberapa probabilitas konstan kecil.$\Omega(n)$$\Omega(n)$

Kita dapat memperbaiki solusi Orlp dengan menggunakan partisi noncrossing . Kami membaca baris demi baris matriks. Untuk setiap baris, kita ingat 1s mana yang terhubung melalui jalur yang melewati baris sebelumnya. Partisi yang sesuai adalah noncrossing, dan karenanya dapat dikodekan menggunakan bit (karena partisi noncrossing dihitung oleh angka Catalan, yang laju pertumbuhannya eksponensial daripada faktorial). Saat membaca baris berikut, kami mempertahankan representasi ini, dan menambah penghitung kapan saja semua ujung beberapa bagian tidak terhubung ke baris saat ini (penghitung mengambil bit ). Seperti dalam solusi Orlp, kami menambahkan deretan angka nol terakhir untuk menyelesaikan pemrosesan matriks. Solusi ini menggunakan$O(n)$$O(\log n)$$O(n)$ bit, yang asimtotik optimal mengingat batas bawah kami.