Jumlah maksimum ikan dalam grid

2658. Jumlah maksimum ikan dalam grid

Kesukaran: Medium

Topik: array, carian kedalaman pertama, carian lebar pertama, mencari kesatuan, matriks

anda diberi grid matriks 2D 0-indexed saiz m x n, di mana (r, c) mewakili:

A tanah
• sel jika grid [r] [c] = 0, atau A air
sel yang mengandungi grid [r] [c] ikan, jika grid [r] [c] & gt; 0.
• Fisher boleh bermula di mana -mana
air

sel (r, c) dan boleh melakukan operasi berikut beberapa kali:

menangkap semua ikan di sel (r, c), atau

bergerak ke mana -mana sel
• sel
.
• kembali
maksimum

bilangan ikan yang boleh ditangkap oleh nelayan jika dia memilih sel permulaannya secara optimum, atau 0 jika tiada sel air wujud

. sel yang bersebelahan sel (r, c), adalah salah satu sel (r, c 1), (r, c - 1), (r 1, c) atau (r - 1, c) Jika wujud.

Contoh 1:

input: grid = [[0,2,1,0], [4,0,0,3], [1,0,0,4], [0,3,2,0] ]

output:

7

• Penjelasan: Fisher boleh bermula pada sel (1,3) dan mengumpul 3 ikan, kemudian pindah ke sel (2,3) dan mengumpul 4 ikan.
• Contoh 2:

input: grid = [[1,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,1] ]

output:

1

Penjelasan:
• Fisher boleh bermula pada sel (0,0) atau (3,3) dan mengumpul satu ikan.
• Kekangan:
• m == grid.length n == grid [i] .length

1 & lt; = m, n & lt; = 10

0 & lt; = grid [i] [j] & lt; = 10

• Petunjuk:
• Jalankan DFS dari setiap sel bukan sifar.
• Setiap kali anda memilih sel untuk bermula dari, tambahkan bilangan ikan yang terkandung dalam sel yang anda lawati.

Penyelesaian:

Masalahnya adalah untuk mencari bilangan maksimum ikan yang dapat ditangkap oleh nelayan dengan memulakan di mana -mana sel air dalam grid. Fisher boleh menangkap ikan di sel semasa dan bergerak ke mana -mana sel air bersebelahan (ke atas, ke bawah, kiri, atau kanan) berulang kali.

1. Mata Utama:

   1. grid mengandungi sel yang sama ada tanah (nilai 0) atau air (nilai & gt; 0).
   2. Fisher hanya boleh bergerak ke sel air bersebelahan.
   3. Objektifnya adalah untuk mencari bilangan maksimum ikan yang boleh dikumpulkan, bermula dari sel air yang terbaik.

   Pendekatan:

   1. Gunakan carian kedalaman-pertama (DFS) untuk meneroka semua laluan yang mungkin bermula dari setiap sel air.
   2. Bagi setiap sel air yang tidak disahkan, jalankan DFS untuk mengira jumlah ikan dalam komponen yang disambungkan.
   3. menjejaki ikan maksimum yang dikumpulkan dari mana -mana komponen yang disambungkan.

   Merancang:

   1. memulakan array 2D yang dikunjungi untuk mengesan sama ada sel telah diterokai.
   2. meleleh melalui setiap sel dalam grid.
   3. Jika sel mengandungi air dan tidak dikunjungi:
      • Jalankan DFS bermula dari sel itu.
      • mengumpulkan jumlah ikan dalam sel air yang disambungkan.
      • Kemas kini ikan maksimum yang dikumpulkan setakat ini.
   4. Kembalikan kiraan ikan maksimum selepas meneroka semua sel.

   mari kita melaksanakan penyelesaian ini dalam php: 2658. Bilangan maksimum ikan dalam grid
   

   <?php /**
    * @param Integer[][] $grid
    * @return Integer
    */
   function findMaxFish($grid) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * Helper function for DFS
    * @param $r
    * @param $c
    * @param $grid
    * @param $visited
    * @param $rows
    * @param $cols
    * @param $directions
    * @return array|bool|int|int[]|mixed|null
    */
   function dfs($r, $c, &$grid, &$visited, $rows, $cols, $directions) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   // Example 1
   grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]];
   echo getMaxFish($grid); // Output: 7
   
   // Example 2
   $grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]];
   echo getMaxFish($grid); // Output: 1
   ?>
   

   Penjelasan:

   Pelaksanaan DFS:

   • untuk setiap sel air (r, c), rekursif meneroka jirannya jika mereka:
     • di dalam sempadan grid.
     • Unvisited.
     • sel air (nilai & gt; 0).
   • mengumpul kiraan ikan semasa rekursi.

   Langkah:

   1. Mula dari sel air dan tandakannya seperti yang dikunjungi.
   2. berulang -ulang melawat jirannya yang sah, menambah kiraan ikan.
   3. Kembalikan jumlah kiraan ikan untuk komponen yang disambungkan.

   Contoh Walkthrough:

   Contoh Input:

   $grid = [
       [0, 2, 1, 0],
       [4, 0, 0, 3],
       [1, 0, 0, 4],
       [0, 3, 2, 0]
   ];
   

   Pelaksanaan:

   1. mulakan pada (1, 3) (nilai = 3). Jalankan DFS:
      • (1, 3) → (2, 3) (nilai = 4).
      • total ikan = 3 4 = 7.
   2. meneroka sel air lain, tetapi tidak ada komponen yang disambungkan mempunyai jumlah ikan yang lebih tinggi.
   3. output: 7.

   Kerumitan masa:

   • dfs traversal: Setiap sel dikunjungi sekali → o (m × n).
   • kerumitan keseluruhan: (m × n), di mana m dan n adalah dimensi grid.

   Output untuk contoh:

   • Contoh 1: 7
   • Contoh 2: 1

   Penyelesaian dengan cekap menggunakan DFS untuk meneroka komponen sel -sel air yang disambungkan dan mengira ikan maksimum yang dapat ditangkap oleh seorang nelayan bermula dari mana -mana sel air. Pendekatan ini memastikan penerokaan optimum dan berfungsi dengan baik untuk kekangan yang diberikan.

   Pautan kenalan

   Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberikan repositori bintang di GitHub atau berkongsi jawatan di rangkaian sosial kegemaran anda? Sokongan anda sangat bermakna bagi saya!

   Jika anda mahukan kandungan yang lebih berguna seperti ini, jangan ragu untuk mengikuti saya:

   • LinkedIn
   • github

Atas ialah kandungan terperinci Jumlah maksimum ikan dalam grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!