2290。最少清除障礙物才能到達轉角
難度:難
主題:陣列、廣度優先搜尋、圖、堆疊(優先權佇列)、矩陣、最短路徑
給你一個 0 索引 大小為 m x n 的 2D 整數陣列網格。每個單元格都有兩個值之一:
- 0 代表空白單元格,
- 1 代表可以移除的障礙物。
您可以在空白儲存格之間向上、向下、向左或向右移動。
將最小個障礙物回到移除,這樣你就可以從左上角(0, 0)移到右下角角(m - 1, n - 1).
範例1:
- 輸入: grid = [[0,1,1],[1,1,0],[1,1,0]]
- 輸出: 2
-
解釋:我們可以移除 (0, 1) 和 (0, 2) 處的障礙物,創造一條從 (0, 0) 到 (2, 2) 的路徑。
- 可以證明我們需要移除至少 2 個障礙物,因此我們返回 2。
- 請注意,可能還有其他方法可以移除 2 個障礙物來建立一條路徑。
範例2:
- 輸入: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
- 輸出: 0
- 解釋:我們可以在不移除任何障礙的情況下從 (0, 0) 移動到 (2, 4),因此我們返回 0。
約束:
- m == grid.length
- n == grid[i].length
- 1 5
- 2 5
- grid[i][j] 為 0 或 1。
- 網格[0][0] == 網格[m - 1][n - 1] == 0
提示:
- 將網格建模為圖形,其中單元格是節點,邊是相鄰單元格之間的。有障礙物的單元格的邊緣的成本為 1,所有其他邊緣的成本為 0。
- 你能使用0-1廣度優先搜尋或Dijkstra演算法嗎?
解:
我們需要使用圖表來模擬這個問題,其中網格中的每個單元格都是一個節點。目標是從左上角 (0, 0) 導航到右下角 (m-1, n-1),同時最大限度地減少我們需要移除的障礙物 (1s) 的數量。
方法:
-
圖形表示:
- 網格中的每個單元格都是一個節點。
- 相鄰單元格之間的移動(上、下、左、右)被視為邊緣。
- 如果一條邊穿過帶有 1(障礙物)的單元格,則成本為 1(移除障礙物),如果它穿過 0(空單元格),則成本為 0。
-
演算法選擇:
- 由於我們需要最小化移除的障礙物數量,因此我們可以使用0-1 BFS(使用雙端隊列的廣度優先搜尋)或Dijkstra 演算法 以及優先級隊列。
- 0-1 BFS 適合這裡,因為每條邊的成本為 0 或 1。
-
0-1 BFS:
- 我們使用deque(雙端佇列)來處理不同成本的節點:
- 將成本為 0 的單元推到雙端隊列的前方。
- 將成本為 1 的單元推到雙端隊列的後面。
- 這個想法是探索網格並始終先擴展不需要移除障礙物的路徑,並且僅在必要時移除障礙物。
- 我們使用deque(雙端佇列)來處理不同成本的節點:
讓我們用 PHP 實作這個解:2290。到達角落所需清除的最小障礙物
解釋:
-
輸入解析:
- 網格被視為二維數組。
- 計算行和列以進行邊界檢查。
-
雙端隊列實作:
- SplDoublyLinkedList用來模擬雙端佇列。支援在前面(unshift)或後面(push)添加元素。
-
已存取陣列:
- 追蹤已造訪過的儲存格以避免冗餘處理。
-
0-1 BFS 邏輯:
- 從 (0, 0) 開始,成本為 0。
- 對於每個相鄰單元格:
- 如果為空(grid[nx][ny] == 0),則以相同的成本將其添加到雙端隊列的前面。
- 如果它是一個障礙物 (grid[nx][ny] == 1),則將其添加到雙端隊列的後面,並增加成本。
-
回傳結果:
- 到達右下角時,回程費用。
- 如果不存在有效路徑(儘管問題保證有一個),則回傳 -1。
複雜:
- 時間複雜度: O(m x n),其中m 是行數,n 是列數。每個單元格都會被處理一次。 空間複雜度:
- O(m x n),對於存取的陣列和雙端隊列。 此實現在給定的限制內有效地工作。
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大! 如果您想要更多類似的有用內容,請隨時關注我:
以上是到達角落所需清除的障礙物最少的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本文討論了PHP中的crypt()和password_hash()的差異,以進行密碼哈希,重點介紹其實施,安全性和對現代Web應用程序的適用性。

文章討論了通過輸入驗證,輸出編碼以及使用OWASP ESAPI和HTML淨化器之類的工具來防止PHP中的跨站點腳本(XSS)。

自動加載PHP會在需要時自動加載類文件,從而通過減少內存使用和增強代碼組織來提高性能。最佳實踐包括使用PSR-4和有效組織代碼。

本文討論了在PHP中管理文件上傳大小的管理,重點是2MB的默認限制以及如何通過修改PHP.INI設置來增加它。

本文討論了PHP 7.1中引入的PHP中的無效類型,允許變量或參數為指定類型或NULL。它突出顯示了諸如提高可讀性,類型安全性和明確意圖的好處,並解釋瞭如何聲明

本文討論了unset()和unlink()功能在編程中的差異,重點關注其目的和用例。 unset()從內存中刪除變量,而unlink()從文件系統中刪除文件。兩者都對效率至關重要


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境

MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

記事本++7.3.1
好用且免費的程式碼編輯器

DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中