Rumah pembangunan bahagian belakang tutorial php Penyingkiran Halangan Minimum untuk Mencapai Sudut

Penyingkiran Halangan Minimum untuk Mencapai Sudut

Dec 01, 2024 am 10:39 AM

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:

Minimum Obstacle Removal to Reach Corner

  • 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:

Minimum Obstacle Removal to Reach Corner

  • 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 <= m, n <= 105
  • 2 <= m * n <= 105
  • 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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

<!--?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

?-->

 

 

 

 

<h3>

   

   

  Penjelasan:

</h3>

 

<ol>

<li>

<p><strong>Penghuraian Input:</strong></p>

 

<ul>

<li>Grid diambil sebagai tatasusunan 2D.</li>

<li>Baris dan lajur dikira untuk semakan sempadan.</li>

</ul>

</li>

<li>

<p><strong>Pelaksanaan Deque:</strong></p>

 

<ul>

<li>

SplDoublyLinkedList digunakan untuk mensimulasikan deque. Ia menyokong penambahan elemen di hadapan (nyah anjakan) atau belakang (tolak).</li>

</ul>

</li>

<li>

<p><strong>Susun Yang Dilawati:</strong></p>

 

<ul>

<li>Menjejaki sel yang telah dilawati untuk mengelakkan pemprosesan berlebihan.</li>

</ul>

</li>

<li>

<p><strong>0-1 BFS Logik:</strong></p>

 

<ul>

<li>Mulakan dari (0, 0) dengan kos 0.</li>

<li>Untuk setiap sel jiran:

 

<ul>

<li>Jika kosong (grid[nx][ny] == 0), tambahkannya pada bahagian hadapan deque dengan kos yang sama.</li>

<li>Jika ia adalah halangan (grid[nx][ny] == 1), tambahkannya ke bahagian belakang deque dengan kos tambahan.</li>

</ul>

</li>

</ul>

</li>

<li>

<p><strong>Kembalikan Keputusan:</strong></p>

 

<ul>

<li>Apabila sudut kanan bawah dicapai, pulangkan kos.</li>

<li>Jika tiada laluan yang sah wujud (walaupun masalah menjamin satu), kembalikan -1.</li>

</ul>

</li>

</ol>

 

 

<hr>

 

<h3>

   

   

  Kerumitan:

</h3>

 

<ul>

<li>

<strong>Kerumitan Masa:</strong> <em><strong>O(m x n)</strong></em>, dengan <em><strong>m</strong></em> ialah bilangan baris dan <em><strong>n</strong></em> ialah bilangan lajur. Setiap sel diproses sekali.</li>

<li>

<strong>Kerumitan Angkasa:</strong> <em><strong>O(m x n)</strong></em>, untuk tatasusunan dan deque yang dilawati.</li>

</ul>

 

<p>Pelaksanaan ini berfungsi dengan cekap dalam kekangan yang diberikan.</p>

 

<p><strong>Pautan Kenalan</strong></p>

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

 

<p>Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:</p>

 

<ul>

<li><strong>LinkedIn</strong></li>

<li><strong>GitHub</strong></li>

</ul>

 

 

           

 

             

   

 

             

         

<p>Atas ialah kandungan terperinci Penyingkiran Halangan Minimum untuk Mencapai Sudut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!</p>

 

 

                        

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

<🎜>: Bubble Gum Simulator Infinity - Cara Mendapatkan dan Menggunakan Kekunci Diraja
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Sistem Fusion, dijelaskan
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Tutorial Java
1664
14
Tutorial PHP
1268
29
Tutorial C#
1248
24
PHP dan Python: Membandingkan dua bahasa pengaturcaraan yang popular PHP dan Python: Membandingkan dua bahasa pengaturcaraan yang popular Apr 14, 2025 am 12:13 AM

PHP dan Python masing -masing mempunyai kelebihan mereka sendiri, dan memilih mengikut keperluan projek. 1.PHP sesuai untuk pembangunan web, terutamanya untuk pembangunan pesat dan penyelenggaraan laman web. 2. Python sesuai untuk sains data, pembelajaran mesin dan kecerdasan buatan, dengan sintaks ringkas dan sesuai untuk pemula.

Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Terangkan hashing kata laluan yang selamat di PHP (mis., Password_hash, password_verify). Mengapa tidak menggunakan MD5 atau SHA1? Apr 17, 2025 am 12:06 AM

Dalam php, kata laluan_hash dan kata laluan 1) password_hash menjana hash yang mengandungi nilai garam untuk meningkatkan keselamatan. 2) Kata Laluan_verify Sahkan kata laluan dan pastikan keselamatan dengan membandingkan nilai hash. 3) MD5 dan SHA1 terdedah dan kekurangan nilai garam, dan tidak sesuai untuk keselamatan kata laluan moden.

PHP dalam Tindakan: Contoh dan aplikasi dunia nyata PHP dalam Tindakan: Contoh dan aplikasi dunia nyata Apr 14, 2025 am 12:19 AM

PHP digunakan secara meluas dalam e-dagang, sistem pengurusan kandungan dan pembangunan API. 1) e-dagang: Digunakan untuk fungsi keranjang belanja dan pemprosesan pembayaran. 2) Sistem Pengurusan Kandungan: Digunakan untuk penjanaan kandungan dinamik dan pengurusan pengguna. 3) Pembangunan API: Digunakan untuk Pembangunan API RESTful dan Keselamatan API. Melalui pengoptimuman prestasi dan amalan terbaik, kecekapan dan pemeliharaan aplikasi PHP bertambah baik.

PHP: Bahasa utama untuk pembangunan web PHP: Bahasa utama untuk pembangunan web Apr 13, 2025 am 12:08 AM

PHP adalah bahasa skrip yang digunakan secara meluas di sisi pelayan, terutamanya sesuai untuk pembangunan web. 1.PHP boleh membenamkan HTML, memproses permintaan dan respons HTTP, dan menyokong pelbagai pangkalan data. 2.PHP digunakan untuk menjana kandungan web dinamik, data borang proses, pangkalan data akses, dan lain -lain, dengan sokongan komuniti yang kuat dan sumber sumber terbuka. 3. PHP adalah bahasa yang ditafsirkan, dan proses pelaksanaan termasuk analisis leksikal, analisis tatabahasa, penyusunan dan pelaksanaan. 4.Php boleh digabungkan dengan MySQL untuk aplikasi lanjutan seperti sistem pendaftaran pengguna. 5. Apabila debugging php, anda boleh menggunakan fungsi seperti error_reporting () dan var_dump (). 6. Mengoptimumkan kod PHP untuk menggunakan mekanisme caching, mengoptimumkan pertanyaan pangkalan data dan menggunakan fungsi terbina dalam. 7

Relevannya PHP: Adakah ia masih hidup? Relevannya PHP: Adakah ia masih hidup? Apr 14, 2025 am 12:12 AM

PHP masih dinamik dan masih menduduki kedudukan penting dalam bidang pengaturcaraan moden. 1) kesederhanaan PHP dan sokongan komuniti yang kuat menjadikannya digunakan secara meluas dalam pembangunan web; 2) fleksibiliti dan kestabilannya menjadikannya cemerlang dalam mengendalikan borang web, operasi pangkalan data dan pemprosesan fail; 3) PHP sentiasa berkembang dan mengoptimumkan, sesuai untuk pemula dan pemaju yang berpengalaman.

Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Bagaimanakah jenis membayangkan jenis PHP, termasuk jenis skalar, jenis pulangan, jenis kesatuan, dan jenis yang boleh dibatalkan? Apr 17, 2025 am 12:25 AM

Jenis PHP meminta untuk meningkatkan kualiti kod dan kebolehbacaan. 1) Petua Jenis Skalar: Oleh kerana Php7.0, jenis data asas dibenarkan untuk ditentukan dalam parameter fungsi, seperti INT, Float, dan lain -lain. 2) Return Type Prompt: Pastikan konsistensi jenis nilai pulangan fungsi. 3) Jenis Kesatuan Prompt: Oleh kerana Php8.0, pelbagai jenis dibenarkan untuk ditentukan dalam parameter fungsi atau nilai pulangan. 4) Prompt jenis yang boleh dibatalkan: membolehkan untuk memasukkan nilai null dan mengendalikan fungsi yang boleh mengembalikan nilai null.

PHP dan Python: Contoh dan perbandingan kod PHP dan Python: Contoh dan perbandingan kod Apr 15, 2025 am 12:07 AM

PHP dan Python mempunyai kelebihan dan kekurangan mereka sendiri, dan pilihannya bergantung kepada keperluan projek dan keutamaan peribadi. 1.PHP sesuai untuk pembangunan pesat dan penyelenggaraan aplikasi web berskala besar. 2. Python menguasai bidang sains data dan pembelajaran mesin.

PHP vs Python: Memahami Perbezaan PHP vs Python: Memahami Perbezaan Apr 11, 2025 am 12:15 AM

PHP dan Python masing -masing mempunyai kelebihan sendiri, dan pilihannya harus berdasarkan keperluan projek. 1.Php sesuai untuk pembangunan web, dengan sintaks mudah dan kecekapan pelaksanaan yang tinggi. 2. Python sesuai untuk sains data dan pembelajaran mesin, dengan sintaks ringkas dan perpustakaan yang kaya.

See all articles