Peta Puncak Tertinggi

1765. Peta Puncak Tertinggi

Kesukaran: Sederhana

Topik: Tatasusunan, Keluasan-Carian Pertama, Matriks

Anda diberi matriks integer ialahAir bersaiz m x n yang mewakili peta sel tanah dan air.

• Jika ialahAir[i][j] == 0, sel (i, j) ialah sel darat.
• Jika ialahAir[i][j] == 1, sel (i, j) ialah sel air.

Anda mesti menetapkan ketinggian setiap sel mengikut peraturan ini:

• Ketinggian setiap sel mestilah bukan negatif.
• Jika sel itu ialah sel air, ketinggiannya mestilah 0.
• Mana-mana dua sel bersebelahan mesti mempunyai perbezaan ketinggian mutlak paling banyak 1. Sebuah sel bersebelahan dengan sel lain jika yang pertama berada di utara, timur, selatan atau barat yang terakhir (iaitu, sisi mereka menyentuh).

Cari penugasan ketinggian supaya ketinggian maksimum dalam matriks adalah dimaksimumkan.

Kembalikan ketinggian matriks integer bersaiz m x n dengan ketinggian[i][j] ialah ketinggian sel (i, j). Jika terdapat berbilang penyelesaian, kembalikan mana-mana daripadanya.

Contoh 1:

• Input: isWater = [[0,1],[0,0]]
• Output: [[1,0],[2,1]]
• Penjelasan: Imej menunjukkan ketinggian yang ditetapkan bagi setiap sel.
  • Sel biru ialah sel air, dan sel hijau ialah sel darat.

Contoh 2:

• Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
• Output: [[1,1,0],[0,1,1],[1,2,2]]
• Penjelasan: Ketinggian 2 ialah ketinggian maksimum yang mungkin bagi mana-mana tugasan.
  • Sebarang tugasan ketinggian yang mempunyai ketinggian maksimum 2 semasa masih mematuhi peraturan juga akan diterima.

Contoh 3:

• Input: ialahAir = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0 ,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0 ,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0, 0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1, 0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0 ,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0 ,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0, 0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0 ,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1 ,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0, 0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1, 0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1 ,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0 ,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0, 0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1 ,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0, 1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0] ,[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1 ,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0 ,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0, 0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0, 0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1 ,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,0 ,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0, 1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1, 0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1 ,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1 ,0,1,1,0,0,0,0,1,0,1,0,0],...]
• Output: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1, 2,1,1,2,2,1,0 ,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1 ,1,2,1,0,1,2, 3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1, 2,1,0,1,1,0,1 ,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1 ,1,0,1,1,2,1, 0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0, 1,1,0,1,0,1,0 ,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2 ,3,2,3,3,2,1, 0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1, 0,1,1,0,1,2], [0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1 ,0,0,1,1,0,0, 1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0, 0,1,2,1,0,1,2 ,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1 ,1,1,1,0,1,0, 1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0, 1,1,1,0,1,0,1 ,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1 ,0,0,1,1,1,0, 0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1, 2,1,2,3,3,2,1 ,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0 ,1,2,1,2,3],[ 1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2, 1,1,0,1,1,1,1 ,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1 ,2,1,...]]

Kekangan:

• m == ialahWater.panjang
• n == ialahAir[i].panjang
• 1
• isWater[i][j] ialah 0 atau 1.
• Terdapat sekurang-kurangnya satu sel air.

Petunjuk:

1. Tetapkan setiap sel air menjadi 0. Ketinggian setiap sel dihadkan oleh sel air terdekatnya.
2. Lakukan BFS berbilang sumber dengan semua sel air sebagai sumber.

Nota: Soalan ini sama dengan 542. 01 Matriks

Penyelesaian:

Kita boleh menggunakan pendekatan carian pertama luas (BFS). Begini cara kita boleh mendekatinya langkah demi langkah:

Pecahan Masalah:

1. Sel Air: Sel dengan 1 mewakili sel air dan ketinggiannya sentiasa 0.
2. Sel Tanah: Sel dengan 0 mewakili sel tanah dan ketinggiannya hendaklah ditetapkan supaya sel tanah bersebelahan mempunyai perbezaan ketinggian paling banyak 1.

Pendekatan:

1. Permulaan BFS:

   • Kita mulakan dengan menandakan semua sel air (sel dengan nilai 1) sebagai titik permulaan dalam BFS dan menetapkan ketinggiannya kepada 0.
   • Kemudian kami memproses sel tanah bersebelahan (sel dengan nilai 0) untuk menetapkan ketinggian.

2. BFS Traversal:

   • Dari setiap sel air, kami mengembang ke luar, meningkatkan ketinggian sebanyak 1 untuk setiap sel darat bersebelahan, memastikan bahawa perbezaan ketinggian antara sel bersebelahan tidak pernah melebihi 1.
   • Kami meneruskan proses ini sehingga semua sel dilawati.

3. Keputusan: Hasilnya ialah matriks ketinggian yang mematuhi peraturan yang diberikan, dengan nilai ketinggian dimaksimumkan.

Mari laksanakan penyelesaian ini dalam PHP: 1765. Peta Puncak Tertinggi

<?php /**
 * @param Integer[][] $isWater
 * @return Integer[][]
 */
function highestPeak($isWater) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$$isWater1 = [[0,1],[0,0]];
$$isWater2 = [[0,0,1],[1,0,0],[0,0,0]];
$$isWater3 = [[1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0],[0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0],...];

echo highestPeak($$isWater1) . "\n"; // Output: [[1,0],[2,1]]
echo highestPeak($$isWater2) . "\n"; // Output: [[1,1,0],[0,1,1],[1,2,2]]
echo highestPeak($$isWater3) . "\n"; // Output: [[0,1,2,2,2,1,0,1,1,0,1,1,0,1,2,1,1,2,2,1,1,0,0,1,2,1,1,2,2,1,0,1,1,0,1,0,0,1,1,0,1,0,1,2,2,1,1,1,0,1,1,1,0,0,1,1,1,2,1,0,1,2,3,2,1,1,0,1,1,0,1,2,2,1,2,2,1,0,1,1,0,1,2,1,0,0,1,2,1,0,1,1,0,1,0,0,1,2,1,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,1,0,1,1,0,1,1,2,1,0,1,0,1,0,0,1,2,1,2,3,3,2,2,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,1,2,1,1,2,2,1,0,0,0,1,0,1,1,2,3,2,2,2,2,2,2,3,2,3,3,2,1,0,1,2,1,1,2,1,0,1,0,0,0,1,1,0,1,2,3,2,1,0,1,2,1,1,0,1,1,0,1,2],[0,0,1,1,2,2,1,0,1,1,1,0,1,2,1,0,0,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,1,0,1,1,2,2,1,0,0,1,1,1,0,1,0,1,1,0,0,1,2,1,0,1,2,1,0,0,1,0,1,0,1,2,1,0,1,1,0,0,0,0,1,2,3,2,1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,0,1,1,1,0,1,0,1,2,1,1,0,0,0,1,0,1,2,2,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,1,2,1,0,0,1,1,0,1,0,1,2,1,1,0,1,2,1,1,1,1,1,1,2,1,2,3,3,2,1,0,1,0,0,1,0,1,0,0,1,0,1,2,1,2,3,2,1,1,0,1,1,0,1,0,1,2,1,2,3],[1,1,0,0,1,1,0,1,1,2,1,0,1,1,1,0,1,0,1,0,1,1,0,1,2,1,1,0,1,1,1,1,0,1,1,2,1,0,1,1,2,1,2,2,1,1,0,1,0,1,0,1,1,2,1,0,1,2,1,...]]
?>

Penjelasan:

1. Permulaan:

   • Kami memulakan matriks ketinggian dengan -1 untuk semua sel. Sel air segera ditetapkan kepada 0.
   • Sel air dimasukkan ke baris gilir BFS.

2. BFS:

   • Kami memproses baris gilir dengan menyah gilir setiap sel, dan untuk setiap sel yang bersebelahan, kami menyemak sama ada ia berada dalam batas dan tidak dilawati.
   • Jika ia sel tanah yang sah (belum dilawati), kami menetapkan ketinggian yang lebih tinggi daripada ketinggian sel semasa dan memasukkannya ke dalam baris gilir untuk pemprosesan selanjutnya.

3. Keputusan:

   • Selepas BFS selesai, matriks ketinggian akan mengandungi ketinggian tertinggi yang mungkin untuk setiap sel, mengikut kekangan yang diberikan.

Kerumitan Masa:

• O(m * n) dengan m ialah bilangan baris dan n ialah bilangan lajur. Ini kerana setiap sel diproses paling banyak sekali semasa traversal BFS.

Penyelesaian ini memastikan bahawa matriks diisi dengan ketinggian yang betul, dan BFS menjamin ketinggian maksimum untuk setiap sel sambil mengekalkan kekangan perbezaan ketinggian antara sel bersebelahan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Peta Puncak Tertinggi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!