Temuduga Pengekodan: Mengira Bilangan Pulau dengan DFS Berulang (Iterative DFS)

Masalah dan Bila Ia Digunakan

Diberikan grid m × n yang hanya mengandungi "1" untuk daratan dan "0" untuk air, kembalikan bilangan pulau. Dua sel daratan bersambung hanya apabila ia berkongsi tepi mendatar atau menegak. Sebuah pulau ialah set sel daratan bersambung yang maksimum.

Kekangannya ialah 1 <= m, n <= 300. Pelaksanaan ini tetap mempertahankan daripada tatasusunan kosong daripada mengubah kontrak pemanggil menjadi kegagalan masa jalanan. Andaikan grid boleh diubah suai. Jika pemanggil mesti mengekalkannya, gunakan matriks visited bersaiz sama sebagai ganti.

Ini ialah soalan algoritma umum untuk pusingan pengekodan kejuruteraan perisian. Ia menguji sama ada calon boleh memodelkan matriks sebagai graf tersirat, merentasi komponen bersambung dan memastikan pelaksanaan konsisten dengan analisis kekompleksan.

Perkara yang Dinilai oleh Penemuduga

Jawapan yang mantap menganggap setiap sel daratan sebagai bucu dan setiap kedekatan daratan empat arah sebagai tepi. Itu menghasilkan peraturan utama: setiap kali imbasan mencapai daratan yang belum dilawati, ia telah menemui komponen bersambung yang baharu. Kira sekali, kemudian rentasi dan tandakan seluruh pulau supaya ia tidak boleh dikira lagi.

Butiran pelaksanaan adalah penting. Tandakan jiran apabila ia ditolak (pushed), bukan apabila ia dikeluarkan (popped); jika tidak, beberapa sel bersebelahan boleh menolak sel yang sama. DFS lelaran mengelakkan tindanan panggilan bahasa yang dalam apabila sebahagian besar grid ialah satu pulau. Jawapan yang tepat juga menyatakan bahawa penandaan setempat (in-place) menghapuskan matriks visited, manakala tindanan eksplisit masih boleh menduduki ruang O(mn) dalam kes terburuk.

Jawapan yang lemah hanya mengatakan "gunakan DFS" tanpa mentakrifkan ketersambungan, mutasi input, invarian ketepatan atau ujian adversari.

Soalan untuk Dijelaskan Terlebih Dahulu

Adakah pepenjuru bersambung? Masalah ini menggunakan empat arah. Jika lapan arah dikira, luaskan senarai arah dan jangkakan beberapa jawapan akan berubah.
Bolehkah input diubah suai? Jika ya, tukar sel "1" yang telah dilawati kepada "0". Jika tidak, gunakan visited, mengekalkan batas masa sambil menambah storan O(mn).
Adakah grid berbentuk segi empat tepat dan tidak kosong? Gesaan menjamin kedua-duanya; kod pengeluaran masih boleh mengembalikan 0 untuk input kosong. Tatasusunan bergerigi (jagged array) memerlukan sempadan berdasarkan setiap baris.
Adakah ini satu pengiraan statik atau pengiraan selepas setiap sisipan daratan? DFS atau BFS sesuai untuk grid statik. Sisipan bertambah lebih memihak kepada disjoint set union.
Apakah had saiz dan tindanan panggilan? Grid 300×300 yang keseluruhannya daratan boleh mendorong laluan dengan 90,000 panggilan rekursif, jadi penyelesaian ini menggunakan tindanan eksplisit.

Rangka Kerja Jawapan 30 Saat

"Saya akan memodelkan sel daratan sebagai bucu dalam graf tersirat, dengan kedekatan empat arah sebagai tepi. Saya mengimbas grid baris demi baris. Setiap 1 yang tinggal memulakan komponen bersambung yang belum diproses, jadi saya menambah kiraan pulau dan menjalankan DFS lelaran daripadanya. Saya menukar jiran daratan kepada 0 semasa menolaknya, yang menghalang penolakan pendua. Setiap sel ditolak paling banyak sekali, dan tindanan eksplisit mengelakkan rekursi yang dalam. Kekompleksan masa ialah O(mn), dan tindanan ialah O(mn) dalam kes terburuk. Jika mutasi dilarang, saya akan menyimpan keadaan yang sama dalam matriks visited."

Perincian Langkah demi Langkah

Langkah 1: Cari kerja berulang dalam carian naif

Memulakan carian baharu dari setiap sel daratan akan merentasi pulau yang sama berkali-kali. Mencari jiran bukanlah kekangan utama; bahagian yang hilang ialah keadaan yang kekal merentasi carian dan merekodkan bahawa sesuatu sel telah tergolong dalam komponen yang dikira.

Imbasan penuh ditambah tanda lawatan kekal menghapuskan pengulangan tersebut. Mulakan traversal hanya dari daratan yang kekal belum dilawati.

Langkah 2: Wujudkan invarian pengiraan

Apabila imbasan mencapai (r, c), setiap DFS sebelumnya telah menandakan tepat satu pulau lengkap. Jika sel semasa masih "1", tiada traversal tersebut yang mencapainya, jadi ia mesti memulakan pulau baharu dan kiraan bertambah sebanyak satu.

DFS hanya mengikut tepi daratan empat arah, jadi ia tidak boleh menyeberangi air dan menggabungkan pulau yang berbeza. Ia juga mencapai setiap sel daratan yang bersambung dengan permulaannya, jadi pulau ini tidak boleh mencetuskan kiraan lain kemudian. Dua fakta tersebut membuktikan kedua-dua tiada pengurangan kiraan dan tiada pengiraan berganda.

Langkah 3: Tandakan semasa menolak

Andaikan sel yang tidak bertanda menyentuh dua sel yang sudah berada dalam tindanan. Jika penandaan menunggu sehingga masa pop, kedua-dua jiran boleh menolak sel tersebut. Hasilnya selalunya masih betul, tetapi tindanan mengandungi kerja pendua dan hujah kekompleksan yang ketat hilang.

Tukar jiran yang ditemui kepada "0" sebelum menolaknya. Sebarang tepi yang memeriksa kemudian akan melihatnya sebagai telah dilawati, menjamin bahawa setiap sel daratan memasuki tindanan paling banyak sekali.

Langkah 4: Laksanakan DFS lelaran

javascript

function numIslands(grid) {
  if (grid.length === 0 || grid[0].length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;

  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] !== "1") continue;

      islands += 1;
      grid[row][col] = "0";
      const stack = [[row, col]];

      while (stack.length > 0) {
        const [currentRow, currentCol] = stack.pop();

        for (const [rowOffset, colOffset] of directions) {
          const nextRow = currentRow + rowOffset;
          const nextCol = currentCol + colOffset;

          if (
            nextRow >= 0 && nextRow < rows &&
            nextCol >= 0 && nextCol < cols &&
            grid[nextRow][nextCol] === "1"
          ) {
            grid[nextRow][nextCol] = "0";
            stack.push([nextRow, nextCol]);
          }
        }
      }
    }
  }

  return islands;
}

Imbasan memeriksa mn sel. Setiap sel daratan ditolak paling banyak sekali dan memeriksa empat jiran, jadi masanya ialah O(mn). Tindanan eksplisit boleh memegang koordinat O(mn) pada grid yang semuanya daratan. Fungsi ini mengubah suai inputnya. Menyalin grid sebagai ganti juga menelan belanja masa dan ruang O(mn).

Langkah 5: Sahkan sempadan dan kes adversari

Sekurang-kurangnya, uji: tatasusunan kosong mengembalikan 0; satu sel air mengembalikan 0; satu sel daratan mengembalikan 1; semua air mengembalikan 0; semua daratan mengembalikan 1; dua sel yang menyentuh secara pepenjuru sahaja mengembalikan 2; sampel dengan tiga wilayah berasingan mengembalikan 3; dan grid 300×300 yang semuanya daratan tidak melimpahkan tindanan panggilan rekursif.

Uji juga kontrak mutasi. Jika penegasan lain memerlukan grid asal selepas panggilan, salin dahulu atau gunakan visited. Pilihan ini tergolong dalam kontrak antara muka, bukan sebagai butiran pelaksanaan tersembunyi.

Langkah 6: Bandingkan alternatif

BFS dan DFS lelaran mempunyai masa dan ruang kes terburuk yang sama di sini. Pilih BFS apabila lapisan jarak penting; mana-mana satu adalah sesuai apabila satu-satunya matlamat adalah untuk menghabiskan komponen. DFS rekursif lebih pendek hanya apabila input cukup kecil atau bahasa menjamin kedalaman yang mencukupi. Disjoint set union berguna apabila daratan tiba secara berperingkat dan kiraan diminta selepas setiap sisipan; ia menambah pengindeksan dan penyelenggaraan set yang tidak perlu untuk satu pengiraan statik.

Contoh Jawapan Berkualiti Tinggi

"Masalah ini ialah pengiraan komponen bersambung dalam graf tidak terarah tersirat. Setiap 1 ialah bucu, dan jiran daratan mendatar atau menegak berkongsi tepi. Saya mengimbas seluruh grid. Jika kedudukan masih 1, tiada carian terdahulu yang mencapainya, jadi saya telah menemui pulau baharu dan menambah kiraan. Saya kemudian menjalankan DFS lelaran dan menukar seluruh pulau itu kepada 0.

Saya menandakan jiran semasa menolaknya supaya dua sel bersebelahan tidak boleh menolak kedudukan yang sama. Saya menggunakan tindanan eksplisit kerana grid 300×300 yang semuanya daratan boleh menghasilkan laluan rekursif yang sangat dalam. Setiap sel diproses paling banyak sekali dan memeriksa empat arah, memberikan masa O(mn) dan ruang tindanan kes terburuk O(mn). Versi ini mengubah suai input; jika antara muka mesti mengekalkannya, saya akan memindahkan tanda ke dalam matriks Boolean visited bersaiz O(mn). Saya akan mengesahkan ketidakbersambungan pepenjuru, semua air, semua daratan dan sempadan input kosong."

Jawapan ini menghubungkan model, hujah pengiraan, risiko pelaksanaan, kesan sampingan dan pengesahan tanpa bergantung pada label yang dihafal.

Kesilapan Biasa

Menganggap pepenjuru bersambung → ini mengubah masalah dan mungkin terkurang kira pulau → kekalkan hanya atas, bawah, kiri dan kanan dalam senarai arah.
Tandakan hanya semasa pop → berbilang jiran boleh menolak sel yang sama → tandakan jiran yang sah serta-merta sebelum menolak.
Mendakwa in-place bermakna ruang O(1) → ini mengabaikan tindanan eksplisit kes terburuk → laporkan O(mn) ruang tambahan dalam kes terburuk.
Gunakan DFS rekursif tanpa membincangkan kedalaman → satu pulau besar boleh menghabiskan tindanan panggilan bahasa → gunakan lelaran atau tetapkan batas saiz yang selamat.
Mengubah suai data pemanggil secara senyap → kod kemudian melihat grid yang telah dibersihkan → dokumentasikan kesan sampingan atau gunakan visited.
Cari lagi dari setiap sel daratan → komponen yang sama diredah berulang kali → mulakan hanya dari daratan yang belum dilawati.
Uji hanya segi empat tepat biasa → contoh balas kosong, semua air, semua daratan dan pepenjuru kekal tidak diuji → tampung kes minimum, ekstrem dan adversari.

Soalan Tindakan Susulan dan Respons

Tindakan Susulan 1: Bagaimana jika input tidak boleh diubah suai?

Peruntukkan matriks Boolean m × n dan tandakan lokasi yang telah dilawati semasa menolaknya. Invarian pengiraan dan masa O(mn) kekal tidak berubah; storan tambahan adalah secara eksplisit O(mn). Menyalin input mempunyai kos ruang asimptotik yang sama tetapi semantik yang berbeza.

Tindakan Susulan 2: Bagaimana jika pepenjuru juga bersambung?

Kembangkan senarai arah daripada empat ofset kepada lapan; rangka kerja traversal tidak berubah. Mula-mula sahkan peraturan dengan kes seperti [[1, 0], [0, 1]]: jawapan empat arah ialah 2, manakala jawapan lapan arah ialah 1.

Tindakan Susulan 3: Bagaimana jika daratan ditambah satu sel pada satu masa dan setiap kiraan diminta?

Mengulangi DFS statik membazirkan kerja. Gunakan disjoint set union sebaliknya: sel daratan baharu pada mulanya meningkatkan kiraan, kemudian bergabung (union) dengan setiap jiran daratan yang sedia ada. Setiap penggabungan yang berjaya bagi dua set berbeza mengurangkan kiraan. Sisipan pendua mesti diabaikan supaya ia tidak bertambah dua kali.

Tindakan Susulan 4: Bagaimana jika julat koordinat sangat besar tetapi daratannya jarang (sparse)?

Jangan peruntukkan matriks penuh. Simpan hanya koordinat daratan dalam set cincangan (hash set), rentasi koordinat tersebut dan siasat empat jiran. Dengan k sel daratan, masa yang dijangkakan ialah O(k), dan set yang dilawati ditambah tindanan ialah O(k). Kesimpulan ini memerlukan perwakilan senarai koordinat jarang (sparse); ia tidak terbit daripada input grid tumpat (dense).