Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid

1368. Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid

Kesukaran: Sukar

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

Diberi grid m x n. Setiap sel grid mempunyai tanda yang menunjuk ke sel seterusnya yang perlu anda lawati jika anda berada dalam sel ini. Tanda grid[i][j] boleh menjadi:

• 1 yang bermaksud pergi ke sel di sebelah kanan. (iaitu pergi dari grid[i][j] ke grid[i][j 1])
• 2 yang bermaksud pergi ke sel di sebelah kiri. (iaitu pergi dari grid[i][j] ke grid[i][j - 1])
• 3 yang bermaksud pergi ke sel bawah. (iaitu pergi dari grid[i][j] ke grid[i 1][j])
• 4 yang bermaksud pergi ke sel atas. (iaitu pergi dari grid[i][j] ke grid[i - 1][j])

Perhatikan bahawa mungkin terdapat beberapa tanda pada sel grid yang menghala ke luar grid.

Anda pada mulanya akan bermula pada sel kiri atas (0, 0). Laluan yang sah dalam grid ialah laluan yang bermula dari sel kiri atas (0, 0) dan berakhir di bahagian bawah sebelah kanan sel (m - 1, n - 1) mengikut tanda pada grid. Laluan yang sah tidak semestinya yang terpendek.

Anda boleh mengubah suai tanda pada sel dengan kos = 1. Anda boleh mengubah suai tanda pada sel sekali sahaja.

Pulangan kos minimum untuk menjadikan grid mempunyai sekurang-kurangnya satu laluan yang sah.

Contoh 1:

• Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2] ]
• Output: 3
• Penjelasan: Anda akan bermula pada titik (0, 0). Laluan ke (3, 3) adalah seperti berikut. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
• tukar anak panah ke bawah dengan kos = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
• tukar anak panah ke bawah dengan kos = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
• tukar anak panah ke bawah dengan kos = 1 --> (3, 3) Jumlah kos = 3.

Contoh 2:

• Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
• Output: 0
• Penjelasan: Anda boleh mengikut laluan dari (0, 0) hingga (2, 2).

Contoh 3:

• Input: grid = [[1,2],[4,3]]
• Output: 1

Kekangan:

• m == grid.panjang
• n == grid[i].panjang
• 1
• 1

Petunjuk:

1. Bina graf di mana grid[i][j] disambungkan kepada semua empat sel bersebelahan sisi dengan tepi berwajaran. beratnya ialah 0 jika tanda itu menunjuk ke sel bersebelahan atau 1 sebaliknya.
2. Lakukan BFS dari (0, 0) lawati semua tepi dengan berat = 0 dahulu. jawapannya ialah jarak ke (m -1, n - 1).

Penyelesaian:

Kita boleh menggunakan pendekatan 0-1 BFS. Ideanya adalah untuk melintasi grid menggunakan deque (baris bersambung dua) di mana kos mengubah suai arah menentukan sama ada sel ditambah ke hadapan atau belakang deque. Grid dianggap sebagai graf di mana setiap sel mempunyai tepi berwajaran berdasarkan sama ada arah semasanya sepadan dengan pergerakan dengan jirannya.

Mari laksanakan penyelesaian ini dalam PHP: 1368. Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid

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

// Example Test Cases
$Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid) . "\n"; // Output: 3

$Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid) . "\n"; // Output: 0

$Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid = [[1,2],[4,3]];
echo minCost($Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid) . "\n"; // Output: 1
?>

Penjelasan:

1. Pemetaan Arah: Setiap arah (1 untuk kanan, 2 untuk kiri, 3 untuk bawah, 4 untuk atas) dipetakan kepada tatasusunan delta pergerakan [dx, dy].

2. 0-1 BFS:

   • Deque digunakan untuk mengutamakan sel dengan kos yang lebih rendah. Sel yang tidak memerlukan pengubahsuaian arah ditambah ke hadapan (nyah anjakan), manakala sel yang memerlukan pengubahsuaian ditambah ke belakang (enqueue).
   • Ini memastikan sel diproses dalam susunan kos yang semakin meningkat.

3. Susun Jarak: Tatasusunan 2D $dist menjejaki kos minimum untuk mencapai setiap sel. Ia dimulakan dengan PHP_INT_MAX untuk semua sel kecuali sel permulaan (0, 0).

4. Berat Tepi:

   • Jika tanda sel semasa sepadan dengan arah yang dimaksudkan, kosnya tetap sama.
   • Jika tidak, mengubah suai arah memerlukan kos sebanyak 1.

5. Penamatan: Gelung ditamatkan sebaik sahaja semua sel telah diproses. Hasilnya ialah nilai dalam $dist[$m - 1][$n - 1], mewakili kos minimum untuk mencapai sudut kanan bawah.

Kerumitan:

• Kerumitan Masa: O(m × n), kerana setiap sel diproses sekali.
• Kerumitan Angkasa: O(m × n), untuk tatasusunan jarak dan deque.

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 Kos Minimum untuk Membuat Sekurang-kurangnya Satu Laluan Sah dalam Grid. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!