搜尋
首頁後端開發php教程到達角落所需清除的障礙物最少

2290。最少清除障礙物才能到達轉角

難度:

主題:陣列、廣度優先搜尋、圖、堆疊(優先權佇列)、矩陣、最短路徑

給你一個 0 索引 大小為 m x n 的 2D 整數陣列網格。每個單元格都有兩個值之一:

  • 0 代表空白單元格,
  • 1 代表可以移除的障礙物

您可以在空白儲存格之間向上、向下、向左或向右移動。

最小障礙物回到移除,這樣你就可以從左上角(0, 0)移到右下角角(m - 1, n - 1).

範例1:

Minimum Obstacle Removal to Reach Corner

  • 輸入: grid = [[0,1,1],[1,1,0],[1,1,0]]
  • 輸出: 2
  • 解釋:我們可以移除 (0, 1) 和 (0, 2) 處的障礙物,創造一條從 (0, 0) 到 (2, 2) 的路徑。
    • 可以證明我們需要移除至少 2 個障礙物,因此我們返回 2。
    • 請注意,可能還有其他方法可以移除 2 個障礙物來建立一條路徑。

範例2:

Minimum Obstacle Removal to Reach Corner

  • 輸入: 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. 將網格建模為圖形,其中單元格是節點,邊是相鄰單元格之間的。有障礙物的單元格的邊緣的成本為 1,所有其他邊緣的成本為 0。
  2. 你能使用0-1廣度優先搜尋或Dijkstra演算法嗎?

解:

我們需要使用圖表來模擬這個問題,其中網格中的每個單元格都是一個節點。目標是從左上角 (0, 0) 導航到右下角 (m-1, n-1),同時最大限度地減少我們需要移除的障礙物 (1s) 的數量。

方法:

  1. 圖形表示:

    • 網格中的每個單元格都是一個節點。
    • 相鄰單元格之間的移動(上、下、左、右)被視為邊緣。
    • 如果一條邊穿過帶有 1(障礙物)的單元格,則成本為 1(移除障礙物),如果它穿過 0(空單元格),則成本為 0。
  2. 演算法選擇:

    • 由於我們需要最小化移除的障礙物數量,因此我們可以使用0-1 BFS(使用雙端隊列的廣度優先搜尋)或Dijkstra 演算法 以及優先級隊列。
    • 0-1 BFS 適合這裡,因為每條邊的成本為 0 或 1。
  3. 0-1 BFS:

    • 我們使用deque(雙端佇列)來處理不同成本的節點:
      • 將成本為 0 的單元推到雙端隊列的前方。
      • 將成本為 1 的單元推到雙端隊列的後面。
    • 這個想法是探索網格並始終先擴展不需要移除障礙物的路徑,並且僅在必要時移除障礙物。

讓我們用 PHP 實作這個解:2290。到達角落所需清除的最小障礙物

解釋:

  1. 輸入解析:

    • 網格被視為二維數組。
    • 計算行和列以進行邊界檢查。
  2. 雙端隊列實作:

    • SplDoublyLinkedList用來模擬雙端佇列。支援在前面(unshift)或後面(push)添加元素。
  3. 已存取陣列:

    • 追蹤已造訪過的儲存格以避免冗餘處理。
  4. 0-1 BFS 邏輯:

    • 從 (0, 0) 開始,成本為 0。
    • 對於每個相鄰單元格:
      • 如果為空(grid[nx][ny] == 0),則以相同的成本將其添加到雙端隊列的前面。
      • 如果它是一個障礙物 (grid[nx][ny] == 1),則將其添加到雙端隊列的後面,並增加成本。
  5. 回傳結果:

    • 到達右下角時,回程費用。
    • 如果不存在有效路徑(儘管問題保證有一個),則回傳 -1。

複雜:

  • 時間複雜度: O(m x n),其中m 是行數,n 是列數。每個單元格都會被處理一次。
  • 空間複雜度:
  • O(m x n),對於存取的陣列和雙端隊列。
  • 此實現在給定的限制內有效地工作。

聯絡連結

如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!

如果您想要更多類似的有用內容,請隨時關注我:

  • 領英
  • GitHub

以上是到達角落所需清除的障礙物最少的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
PHP記錄:PHP日誌分析的最佳實踐PHP記錄:PHP日誌分析的最佳實踐Mar 10, 2025 pm 02:32 PM

PHP日誌記錄對於監視和調試Web應用程序以及捕獲關鍵事件,錯誤和運行時行為至關重要。它為系統性能提供了寶貴的見解,有助於識別問題並支持更快的故障排除

在Laravel中使用Flash會話數據在Laravel中使用Flash會話數據Mar 12, 2025 pm 05:08 PM

Laravel使用其直觀的閃存方法簡化了處理臨時會話數據。這非常適合在您的應用程序中顯示簡短的消息,警報或通知。 默認情況下,數據僅針對後續請求: $請求 -

php中的捲曲:如何在REST API中使用PHP捲曲擴展php中的捲曲:如何在REST API中使用PHP捲曲擴展Mar 14, 2025 am 11:42 AM

PHP客戶端URL(curl)擴展是開發人員的強大工具,可以與遠程服務器和REST API無縫交互。通過利用Libcurl(備受尊敬的多協議文件傳輸庫),PHP curl促進了有效的執行

簡化的HTTP響應在Laravel測試中模擬了簡化的HTTP響應在Laravel測試中模擬了Mar 12, 2025 pm 05:09 PM

Laravel 提供简洁的 HTTP 响应模拟语法,简化了 HTTP 交互测试。这种方法显著减少了代码冗余,同时使您的测试模拟更直观。 基本实现提供了多种响应类型快捷方式: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

在Codecanyon上的12個最佳PHP聊天腳本在Codecanyon上的12個最佳PHP聊天腳本Mar 13, 2025 pm 12:08 PM

您是否想為客戶最緊迫的問題提供實時的即時解決方案? 實時聊天使您可以與客戶進行實時對話,並立即解決他們的問題。它允許您為您的自定義提供更快的服務

解釋PHP中晚期靜態結合的概念。解釋PHP中晚期靜態結合的概念。Mar 21, 2025 pm 01:33 PM

文章討論了PHP 5.3中介紹的PHP中的晚期靜態結合(LSB),允許靜態方法的運行時間分辨率調用以更靈活的繼承。 LSB的實用應用和潛在的觸摸

自定義/擴展框架:如何添加自定義功能。自定義/擴展框架:如何添加自定義功能。Mar 28, 2025 pm 05:12 PM

本文討論了將自定義功能添加到框架上,專注於理解體系結構,識別擴展點以及集成和調試的最佳實踐。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

SecLists

SecLists

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