Description
給定一個
n x n的二維網格grid，其中0代表可通行、1代表障礙。求從左上角(0,0)到右下角(n-1,n-1)的最短路徑長度（可沿 8 個方向移動）。路徑長度為經過的格子數。
Example:
Input: grid = [[0,1],[1,0]] Output: 2
Intuition#
等權圖最短路徑 – BFS 從左上到右下，允許八方向移動。
- 可沿 8 個方向移動（含對角線）
- BFS 天然找到最短路徑（每步權重相同）
- 路徑長度是格子數，不是邊數
Approaches#
⭐1: BFS#
- 概念: 從
(0,0)開始 BFS，每步向 8 個方向擴展，第一次到達(n-1,n-1)即為最短路徑 - 時間複雜度:
O(n^2) - 空間複雜度:
O(n^2)
class Solution {
fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
val n = grid.size
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1
if (n == 1) return 1
val queue = ArrayDeque<IntArray>()
queue.add(intArrayOf(0, 0))
grid[0][0] = 1
var length = 1
while (queue.isNotEmpty()) {
length++
repeat(queue.size) {
val (r, c) = queue.removeFirst()
for (dr in -1..1) {
for (dc in -1..1) {
if (dr == 0 && dc == 0) continue
val nr = r + dr
val nc = c + dc
if (nr in 0 until n && nc in 0 until n && grid[nr][nc] == 0) {
if (nr == n - 1 && nc == n - 1) return length
grid[nr][nc] = 1
queue.add(intArrayOf(nr, nc))
}
}
}
}
}
return -1
}
}2: A* 搜尋#
- 概念: 用 A* 搜尋加速，啟發函式為切比雪夫距離
max(|dr|, |dc|) - 時間複雜度:
O(n^2 log n) - 空間複雜度:
O(n^2)
class Solution {
fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int {
val n = grid.size
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1
if (n == 1) return 1
val dist = Array(n) { IntArray(n) { Int.MAX_VALUE } }
dist[0][0] = 1
// [estimated total, distance, row, col]
val pq = java.util.PriorityQueue<IntArray>(compareBy { it[0] })
pq.add(intArrayOf(maxOf(n - 1, n - 1), 1, 0, 0))
while (pq.isNotEmpty()) {
val (_, d, r, c) = pq.poll()
if (r == n - 1 && c == n - 1) return d
if (d > dist[r][c]) continue
for (dr in -1..1) {
for (dc in -1..1) {
if (dr == 0 && dc == 0) continue
val nr = r + dr
val nc = c + dc
if (nr in 0 until n && nc in 0 until n && grid[nr][nc] == 0 && d + 1 < dist[nr][nc]) {
dist[nr][nc] = d + 1
val h = maxOf(n - 1 - nr, n - 1 - nc)
pq.add(intArrayOf(d + 1 + h, d + 1, nr, nc))
}
}
}
}
return -1
}
}🔑 Takeaways#
- Pattern: 網格 BFS 最短路徑 – 8 方向移動
- 關鍵技巧: 路徑長度是格子數（起點也算）；原地標記可避免額外 visited 陣列；A* 的切比雪夫距離啟發函式適用於 8 方向移動