Penyingkiran Halangan Minimum untuk Mencapai Sudut

2290. Penyingkiran Halangan Minimum untuk Mencapai Sudut

Kesukaran: Sukar

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

Anda diberikan grid tatasusunan integer 2D 0-diindeks bersaiz m x n. Setiap sel mempunyai satu daripada dua nilai:

• 0 mewakili sel kosong,
• 1 mewakili halangan yang mungkin dialih keluar.

Anda boleh bergerak ke atas, bawah, kiri atau kanan dari dan ke sel kosong.

Kembalikan bilangan minimum halangan untuk alih keluar supaya anda boleh bergerak dari sudut kiri atas (0, 0) ke kanan bawah sudut (m - 1, n - 1).

Contoh 1:

• Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
• Output: 2
• Penjelasan: Kita boleh mengalih keluar halangan di (0, 1) dan (0, 2) untuk mencipta laluan dari (0, 0) hingga (2, 2).
  • Ia boleh ditunjukkan bahawa kita perlu mengeluarkan sekurang-kurangnya 2 halangan, jadi kita kembali 2.
  • Perhatikan bahawa mungkin terdapat cara lain untuk mengalih keluar 2 halangan untuk mencipta laluan.

Contoh 2:

• Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
• Output: 0
• Penjelasan: Kita boleh bergerak dari (0, 0) ke (2, 4) tanpa mengalih keluar sebarang halangan, jadi kita kembali 0.

Kekangan:

• m == grid.panjang
• n == grid[i].panjang
• 1 5
• 2 5
• grid[i][j] ialah sama ada 0 atau 1.
• grid[0][0] == grid[m - 1][n - 1] == 0

Petunjuk:

1. Modelkan grid sebagai graf di mana sel adalah nod dan tepi berada di antara sel bersebelahan. Tepi ke sel dengan halangan mempunyai kos 1 dan semua tepi lain mempunyai kos 0.
2. Bolehkah anda menggunakan 0-1 Breadth-First Search atau algoritma Dijkstra?

Penyelesaian:

Kita perlu memodelkan masalah ini menggunakan graf di mana setiap sel dalam grid ialah nod. Matlamatnya adalah untuk menavigasi dari sudut kiri atas (0, 0) ke sudut kanan bawah (m-1, n-1), sambil meminimumkan bilangan halangan (1s) yang perlu kami alih keluar.

Pendekatan:

1. Perwakilan Graf:

   • Setiap sel dalam grid ialah nod.
   • Pergerakan antara sel bersebelahan (atas, bawah, kiri, kanan) dianggap sebagai tepi.
   • Jika tepi bergerak melalui sel dengan 1 (halangan), kosnya ialah 1 (alih keluar halangan), dan jika ia bergerak melalui 0 (sel kosong), kosnya ialah 0.

2. Pilihan Algoritma:

   • Memandangkan kita perlu meminimumkan bilangan halangan yang dialih keluar, kita boleh menggunakan 0-1 BFS (Breadth-First Search dengan deque) atau Algoritma Dijkstra dengan baris gilir keutamaan.
   • 0-1 BFS sesuai di sini kerana setiap tepi mempunyai kos sama ada 0 atau 1.

3. 0-1 BFS:

   • Kami menggunakan deque (baris bersambung dua) untuk memproses nod dengan kos yang berbeza:
     • Tolak sel dengan kos 0 ke hadapan deque.
     • Tolak sel dengan kos 1 ke belakang deque.
   • Ideanya adalah untuk meneroka grid dan sentiasa mengembangkan laluan yang tidak memerlukan penyingkiran halangan terlebih dahulu, dan hanya mengalih keluar halangan apabila perlu.

Mari laksanakan penyelesaian ini dalam PHP: 2290. Penyingkiran Halangan Minimum untuk Mencapai Sudut

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

// Test Case 1
$grid1 = [
    [0, 1, 1],
    [1, 1, 0],
    [1, 1, 0]
];
echo minimumObstacles($grid1) . PHP_EOL; // Output: 2

// Test Case 2
$grid2 = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
];
echo minimumObstacles($grid2) . PHP_EOL; // Output: 0
?>

Penjelasan:

1. Penghuraian Input:

   • Grid diambil sebagai tatasusunan 2D.
   • Baris dan lajur dikira untuk semakan sempadan.

2. Pelaksanaan Deque:

   • SplDoublyLinkedList digunakan untuk mensimulasikan deque. Ia menyokong penambahan elemen di hadapan (nyah anjakan) atau belakang (tolak).

3. Susun Yang Dilawati:

   • Menjejaki sel yang telah dilawati untuk mengelakkan pemprosesan berlebihan.

4. 0-1 BFS Logik:

   • Mulakan dari (0, 0) dengan kos 0.
   • Untuk setiap sel jiran:
     • Jika kosong (grid[nx][ny] == 0), tambahkannya pada bahagian hadapan deque dengan kos yang sama.
     • Jika ia adalah halangan (grid[nx][ny] == 1), tambahkannya ke bahagian belakang deque dengan kos tambahan.

5. Kembalikan Keputusan:

   • Apabila sudut kanan bawah dicapai, pulangkan kos.
   • Jika tiada laluan yang sah wujud (walaupun masalah menjamin satu), kembalikan -1.

---

Kerumitan:

• Kerumitan Masa: O(m x n), dengan m ialah bilangan baris dan n ialah bilangan lajur. Setiap sel diproses sekali.
• Kerumitan Angkasa: O(m x n), untuk tatasusunan dan deque yang dilawati.

Pelaksanaan ini berfungsi dengan cekap dalam kekangan yang diberikan.

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 Penyingkiran Halangan Minimum untuk Mencapai Sudut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!