最短路徑
#最短路徑含有「最短路徑」共 9 篇內容
全部內容
發佈日期由新至舊
合縱連橫: 從 圖論的應用題 理解BFS背後的本質這篇文章，會帶著大家複習以前學過的BFS框架，
並且以圖論的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
BFS 框架 + 演算法 虛擬碼
# Queue 通常初始化成根結點，作為起點
BFS_queue = deque([root])
# 先
2024-04-02
10
圖論應用: 壞掉的橘子 Rotting Oranges_Leetcode #994_精選75題題目敘述
題目會給定一個二維陣列grid，代表每顆橘子分布的位置和初始狀態。
0: 這個格子點沒有東西。
1: 這個格子點有一顆新鮮的橘子。
2: 這個格子點有一顆壞掉的橘子。
壞掉的橘子上面的黴菌，
每隔一個週期，可以向上、下、左、右 N4四連通的格子點感染一次。
請問，最少需要多
2024-02-26
4
進階圖論應用: 解開數字鎖 Open the Lock_Leetcode #752題目敘述
題目會給我們一個4位數字的數字鎖，還有解鎖的密碼target，和陷阱數字deadends(假如遇到的會鎖會直接卡住，不能在撥動轉盤了)。
預設開始的狀態是0000，請問，最少要撥動轉盤幾次才能解鎖?
題目的原文敘述
測試範例
Example 1:
Input: deaden
2024-02-09
5
圖論:最接近的迷宮出口 Nearest Exit from Entrance in Maze_Leetcode 1926題目敘述
題目給定一個二維陣列maze代表迷宮的布局，
其中標記為"."的地方代表可通過，標記為"+"代表牆壁不可通過。
每次移動的時候，可以選擇往上、下、左、右移動一格。
請問從出發點entrace開始走的話，抵達迷宮出口最短距離的步數是多少？
如果無解的話，返回-1。
題目的原文敘述
2024-02-09
3
最短路徑應用: 遊戲模擬 Jump Game IV 青蛙過河 IV_Leetcode_#1345題目敘述
題目會給我們一個輸入陣列arr，起始點固定在索引為0的位置，
終點固定在索引為n-1的位置。
假設當下所在的索引位置為i，那麼每次移動的時候，可以跳到i-1，i+1，或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。
例如:
假設當下在i=3
2024-01-28
6
判斷是否能在時間限制內抵達終點 Leetcode #2849題目會給定我們兩個點座標，分別是起點和終點。
另外，還有一個參數t，代表時間限制。
從起點出發之後，每一秒鐘，我們必須選擇一個N8 8連通的方向，往鄰居的格子點移動。(題目有特別強調，每一秒必須強制移動到下一個格子點，不能停留在原地)
請問我們能不能在時間限制內，從起點走到終點?
2023-11-08
3
