Masa Minimum untuk Melawat Sel Dalam Grid

2577. Masa Minimum untuk Melawat Sel Dalam Grid

Kesukaran: Sukar

Topik: Tatasusunan, Keluasan Carian Pertama, Graf, Timbunan (Baris Gilir Keutamaan), Matriks, Laluan Terpendek

Anda diberi grid matriks m x n yang terdiri daripada bukan negatif integer dengan grid[row][col] mewakili minimum masa yang diperlukan untuk dapat melawati sel (baris, col), yang bermaksud anda boleh melawati sel (baris, kol) hanya apabila masa anda melawatinya lebih besar daripada atau sama dengan grid[baris][col].

Anda berdiri di kiri atas sel matriks dalam 0^ke saat, dan anda mesti beralih ke mana-mana sel bersebelahan dalam empat arah: atas, bawah, kiri dan kanan. Setiap pergerakan yang anda lakukan mengambil masa 1 saat.

Kembalikan masa minimum yang diperlukan di mana anda boleh melawati sel sebelah kanan bawah matriks. Jika anda tidak dapat melawati sel sebelah kanan bawah, kemudian kembalikan -1.

Contoh 1:

• Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
• Output: 7
• Penjelasan: Salah satu jalan yang boleh kita lalui adalah seperti berikut:
  • pada t = 0, kita berada di sel (0,0).
  • pada t = 1, kita beralih ke sel (0,1). Ia mungkin kerana grid[0][1] <= 1.
  • pada t = 2, kita bergerak ke sel (1,1). Ia mungkin kerana grid[1][1] <= 2.
  • pada t = 3, kita bergerak ke sel (1,2). Ia mungkin kerana grid[1][2] <= 3.
  • pada t = 4, kita bergerak ke sel (1,1). Ia mungkin kerana grid[1][1] <= 4.
  • pada t = 5, kita bergerak ke sel (1,2). Ia mungkin kerana grid[1][2] <= 5.
  • pada t = 6, kita bergerak ke sel (1,3). Ia mungkin kerana grid[1][3] <= 6.
  • pada t = 7, kita bergerak ke sel (2,3). Ia mungkin kerana grid[2][3] <= 7.
  • Masa terakhir ialah 7. Ia boleh ditunjukkan bahawa ia adalah masa minimum yang mungkin.

Contoh 2:

• Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
• Output: -1
• Penjelasan: Tiada laluan dari kiri atas ke sel kanan bawah.

Kekangan:

• m == grid.panjang
• n == grid[i].panjang
• 2 <= m, n <= 1000
• 4 <= m * n <= 10>sup>5
• 0 <= grid[i][j] <= 10>sup>5
• grid[0][0] == 0

Petunjuk:

1. Cuba gunakan beberapa algoritma yang boleh mencari laluan terpendek pada graf.
2. Pertimbangkan kes di mana anda perlu berulang-alik antara dua sel matriks untuk membuka kunci beberapa sel lain.

Penyelesaian:

Kami boleh menggunakan versi algoritma Dijkstra yang diubah suai menggunakan baris gilir keutamaan. Masalah ini pada asasnya meminta kami mencari masa terpendek yang diperlukan untuk melawati sel kanan bawah dari sel kiri atas, di mana setiap pergerakan mempunyai kekangan masa berdasarkan nilai dalam grid.

Pendekatan:

1. Perwakilan Graf: Anggap setiap sel dalam grid sebagai nod. Tepi ialah sel bersebelahan (atas, bawah, kiri, kanan) yang boleh anda alihkan.

2. Baris Gilir Keutamaan (Timbunan Min): Gunakan baris gilir keutamaan untuk sentiasa meneroka sel dengan masa yang paling singkat. Ini memastikan bahawa kami memproses sel mengikut urutan masa terawal kami boleh mencapainya.

3. BFS yang diubah suai: Untuk setiap sel, kami akan menyemak sama ada kami boleh berpindah ke sel jirannya dan mengemas kini masa kami boleh melawatinya. Jika sel dilawati lebih lewat daripada semasa, kami menambahnya semula ke dalam baris gilir dengan masa baharu.

4. Keluar Awal: Sebaik sahaja kami sampai ke sel kanan bawah, kami boleh mengembalikan masa. Jika kita meletihkan barisan tanpa mencapainya, kembalikan -1.

Mari laksanakan penyelesaian ini dalam PHP: 2577. Masa Minimum untuk Melawat Sel Dalam Grid

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

Penjelasan:

1. Baris Gilir Keutamaan:
   
   SplPriorityQueue digunakan untuk memastikan bahawa sel dengan masa minimum diproses terlebih dahulu. Keutamaan disimpan sebagai -time kerana SplPriorityQueue PHP ialah timbunan maksimum secara lalai.

2. Perjalanan:
   
   Bermula dari sel kiri atas (0, 0), algoritma memproses semua sel yang boleh dicapai, dengan mengambil kira masa paling awal setiap sel boleh dilawati (maks(0, grid[newRow][newCol] - (masa 1))).

3. Sel yang Dilawati:
   
   Tatasusunan yang dilawati menjejaki sel yang telah diproses untuk mengelakkan pengiraan berlebihan dan gelung tak terhingga.

4. Semakan Sempadan dan Kesahan:
   
   Algoritma memastikan kami berada dalam lingkungan grid dan hanya memproses jiran yang sah.

5. Pengiraan Masa:
   
   Setiap pergerakan mengambil masa satu saat dan jika sel memerlukan menunggu (iaitu, grid[newRow][newCol] > masa 1), algoritma menunggu sehingga masa yang diperlukan.

6. Sarung Tepi:
   
   Jika baris gilir habis dan sel kanan bawah tidak dicapai, fungsi mengembalikan -1.

---

Analisis Kerumitan

1. Kerumitan Masa:

   • Setiap sel ditambahkan pada baris gilir keutamaan paling banyak sekali: O(m x n x log(m x n)), di mana m dan n ialah dimensi grid.

2. Kerumitan Angkasa:

   • Ruang untuk baris gilir keutamaan dan tatasusunan yang dilawati ialah O(m x n).

---

Contoh Larian

Input:

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

Input:

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

Penyelesaian ini cekap dan berfungsi dengan baik dalam kekangan.

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 Masa Minimum untuk Melawat Sel Dalam Grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!