BFS — 實戰題解
範圍 — BFS 的題目集：每一題經典的逐層、多源、狀態空間與「把樹當成圖」的題目各一張 problem card，各自歸在它所歸約到的 bfs.md 模板之下 —— 這裡不教任何自己的模板。 另見：bfs.md — 這裡每張 card 所歸約到的模板；bfs_advanced.md — 比較少見的 BFS 變形（雙向、0-1 雙端佇列、以路線為節點、列舉所有最短路徑、擴充狀態）。
LeetCode 題目清單
總覽
經典的 BFS 題目，依每題所歸約到的 bfs.md 模板分組，順序和那份文件的模板順序相同。 每張 card 只講它在模板之上多加的那一步；模板本身一點就到。在別份文件裡解過的題目，這裡只在 Index 留一列指標。Template 3（帶方向陣列的格子 BFS）在這裡沒有自己的 card：它的格子題不是從 很多格同時出發（Template 4），就是錨定題 LC 1091 本身。
索引
| LC | 題目 | 歸約到 | 難度 |
|---|---|---|---|
| 116 / 117 | Populating Next Right Pointers in Each Node | bfs § Template 1 | Medium |
| 958 | Check Completeness of a Binary Tree | bfs § Template 1 | Medium |
| 623 | Add One Row to Tree | bfs § Template 1 | Medium |
| 662 | Maximum Width of Binary Tree | bfs § Template 1 | Medium |
| 909 | Snakes and Ladders | bfs § Template 2 | Medium |
| 207 | Course Schedule | graph § Template 4 — 在那裡解 | Medium |
| 286 | Walls and Gates | bfs § Template 4 | Medium |
| 130 | Surrounded Regions | bfs § Template 4 | Medium |
| 994 | Rotting Oranges | bfs § Template 4 — 錨定題，在那裡解 | Medium |
| 417 | Pacific Atlantic Water Flow | 在 dfs_examples.md 解 | Medium |
| 310 | Minimum Height Trees | 在 topology_sorting_examples.md 解（剝葉子） | Medium |
| 752 | Open the Lock | bfs § Template 5 | Medium |
| 279 | Perfect Squares | bfs § Template 5 | Medium |
| 773 | Sliding Puzzle | bfs § Template 5 | Hard |
| 742 | Closest Leaf in a Binary Tree | bfs § Template 6 | Medium |
| 863 | All Nodes Distance K in Binary Tree | bfs § Template 6 — 錨定題，在那裡解 | Medium |
逐層 BFS 的題目
Populating Next Right Pointers in Each Node — LC 116 / 117
關鍵 —
next是「同一層裡在我右邊的節點」，正好就是逐層 BFS 彈出一層的順序：把每個彈出的 節點接到下一個彈出的節點，一層的最後一個節點維持next = None。完全沒用到樹的形狀，所以同一份 程式碼同時解 LC 116（完美二元樹）與 LC 117（任意樹）。
歸約到：bfs § Template 1 — 在一層之內多帶一個 prev 指標。
python
# python
# LC 116 / 117 - Populating Next Right Pointers in Each Node
# IDEA: level-order BFS; inside one level, link prev.next = node in pop order
# time = O(n), space = O(w) w = the widest level
from collections import deque
def connect(root):
if not root:
return None
queue = deque([root])
while queue:
prev = None
for _ in range(len(queue)): # exactly one level
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
prev.next = None # the last node of a level points nowhere
return root
追問要 O(1) 額外空間。在完美二元樹（LC 116）上，剛接好的那一層本身就是一條鏈結串列，所以
順著 next 走它，就能接好下一層 —— 複雜度不同，所以保留：
python
# python
# LC 116 - Populating Next Right Pointers in Each Node (O(1) space, perfect tree only)
# IDEA: walk level L through the next links it already has, and wire level L + 1
# time = O(n), space = O(1)
def connect_constant_space(root):
if not root:
return None
leftmost = root
while leftmost.left: # stop at the leaf level
head = leftmost
while head:
head.left.next = head.right # two children of one parent
if head.next:
head.right.next = head.next.left # across two parents
head = head.next
leftmost = leftmost.left
return root
陷阱
- O(1) 版本假設每個節點都有兩個子節點；在 LC 117 上會去存取不存在的子節點。LC 117 的 O(1) 版本 要改成每層一個 dummy head。
prev每一層開頭都要重設，否則上一層的最後一個節點會接到下一層的第一個節點。
相似題 — LC 199（每層最後一個節點） · LC 102（基本迴圈）
Check Completeness of a Binary Tree — LC 958
關鍵 — 連
None子節點也入列。佇列這時讀出來就是樹的陣列表示法，而完全二元樹的所有None都在尾端：一旦彈出過None，之後再出現任何真的節點就代表中間有洞。
歸約到：bfs § Template 1 — 不需要逐層迴圈，而且 None 子節點留在佇列裡。
python
# python
# LC 958 - Check Completeness of a Binary Tree
# IDEA: push children unconditionally; after the first None pops, a real node means "not complete"
# time = O(n), space = O(w)
from collections import deque
def isCompleteTree(root):
queue = deque([root])
seen_null = False
while queue:
node = queue.popleft()
if node is None:
seen_null = True
else:
if seen_null:
return False # a real node after a gap
queue.append(node.left) # None children are enqueued on purpose
queue.append(node.right)
return True
陷阱
- 只檢查「除了最後一層都是滿的」會漏掉
[1,2,3,4,5,null,7]：最後一層中間有洞。 - 逐層序列化（LC 297）寫出
null標記也是同樣的理由；這裡就是把那個佇列讀回來。
相似題 — LC 297（用 null 標記序列化） · LC 222（計算完全二元樹的節點數）
Add One Row to Tree — LC 623
關鍵 — 要改的是第
depth - 1層，也就是子指標會變的那個父層。逐層 BFS 走到佇列剛好裝著 那一層，就幫其中每個節點掛兩個新子節點，並把舊的子樹掛在外側。depth == 1沒有父層，所以 新節點直接當根。
歸約到：bfs § Template 1 — 停在某一層把它重接，而不是繼續往下走。
python
# python
# LC 623 - Add One Row to Tree
# IDEA: level BFS down to depth - 1; splice new nodes under each node there, old subtrees outside
# time = O(n), space = O(w)
from collections import deque
def addOneRow(root, val, depth):
if depth == 1: # no parent row: the new node is the root
return TreeNode(val, root, None)
queue = deque([root])
cur_depth = 1 # the root is depth 1, not 0
while queue:
if cur_depth == depth - 1: # the queue holds exactly the parent row
for node in queue:
node.left = TreeNode(val, node.left, None) # old left goes on the left
node.right = TreeNode(val, None, node.right) # old right goes on the right
return root
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
cur_depth += 1
return root
帶著深度往下走的 DFS 比較短，空間是 O(h) 而不是 O(w) —— 因為這點而保留：
python
# python
# LC 623 - Add One Row to Tree (DFS)
# IDEA: recurse with the current depth; at depth - 1 rewire the two children and stop
# time = O(n), space = O(h)
def addOneRow_dfs(root, val, depth):
if depth == 1:
return TreeNode(val, root, None)
def insert(node, d):
if not node:
return
if d == depth - 1:
node.left = TreeNode(val, node.left, None)
node.right = TreeNode(val, None, node.right)
return # never descend into the new nodes
insert(node.left, d + 1)
insert(node.right, d + 1)
insert(root, 1)
return root
陷阱
- 停在
cur_depth == depth已經晚了一層：要改的指標在父層上。 - 把舊子樹掛在內側（
new_left.right = old_left）會讓子樹左右鏡像。 - 重接之後還繼續 BFS，會走進新建的
val節點。 - 歪斜樹上
depth可達 10⁴，超過 Python 預設的遞迴上限；BFS 寫法沒有這個限制。
相似題 — LC 199（同樣的逐層迴圈） · LC 226（先存再換子指標）
Maximum Width of Binary Tree — LC 662
關鍵 — 給每個節點它的 heap 索引（
i的子節點是2i與2i + 1）；一層的寬度是last - first + 1，這樣就把None的空隙算進去卻不用存它們。每一層的索引都要減掉該層第一個 索引，否則深度約 60 的歪斜樹會讓int溢位。
歸約到：bfs § Template 1 — 佇列裡放 (node, index)。
python
# python
# LC 662 - Maximum Width of Binary Tree
# IDEA: level BFS carrying a heap index, re-based to 0 at the start of every level
# time = O(n), space = O(w)
from collections import deque
def widthOfBinaryTree(root):
if not root:
return 0
best = 0
queue = deque([(root, 0)])
while queue:
first = queue[0][1]
last = 0
for _ in range(len(queue)):
node, idx = queue.popleft()
idx -= first # re-base: this level now starts at 0
last = idx
if node.left:
queue.append((node.left, 2 * idx))
if node.right:
queue.append((node.right, 2 * idx + 1))
best = max(best, last + 1)
return best
java
// java
// LC 662 - Maximum Width of Binary Tree
// IDEA: level BFS carrying a heap index; width = last - first + 1 (nulls counted implicitly)
// time = O(n), space = O(w)
public int widthOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int ans = 0;
Queue<TreeNode> nodes = new LinkedList<>();
Queue<Integer> idxs = new LinkedList<>();
nodes.offer(root); idxs.offer(0);
while (!nodes.isEmpty()) {
int size = nodes.size(), first = 0, last = 0;
for (int i = 0; i < size; i++) {
TreeNode node = nodes.poll();
int id = idxs.poll();
if (i == 0) first = id;
id -= first; // re-base the level at 0 -> no overflow
last = id;
if (node.left != null) { nodes.offer(node.left); idxs.offer(2 * id); }
if (node.right != null) { nodes.offer(node.right); idxs.offer(2 * id + 1); }
}
ans = Math.max(ans, last + 1); // last is already relative to first
}
return ans;
}
前序 DFS 不需要佇列：它最先碰到每一層最左邊的節點，所以記住那個索引，之後同一層的節點都從它 量起 —— 空間是 O(h) 而不是 O(w)：
python
# python
# LC 662 - Maximum Width of Binary Tree (DFS)
# IDEA: heap index (2p, 2p + 1); pre-order meets each depth's leftmost node first, so remember it
# time = O(n), space = O(h)
def widthOfBinaryTree_dfs(root):
first = {} # depth -> heap index of the leftmost node there
best = 0
def dfs(node, depth, pos):
nonlocal best
if not node:
return
first.setdefault(depth, pos)
best = max(best, pos - first[depth] + 1)
dfs(node.left, depth + 1, 2 * pos)
dfs(node.right, depth + 1, 2 * pos + 1)
dfs(root, 0, 0)
return best
陷阱
- 沒有重新歸零，Java 在 3,000 個節點的鋸齒鏈上會溢位；Python 不會溢位，但整數會長到幾千個位元。
DFS 寫法沒辦法每層歸零，所以在 Java 裡要用
long，或減掉該深度的第一個索引。 - 只數每層非空節點，得到的是該層的節點數，不是寬度。
相似題 — LC 958（同樣用 heap 索引看樹） · LC 102
圖 BFS 的題目
Snakes and Ladders — LC 909
關鍵 — 棋盤就是格子
1 … n²上的一張圖：從格子s各有一條邊連到s + 1 … s + 6，若落點 有蛇或梯子就改道。每擲一次都是一步，所以普通 BFS 給出最少擲骰次數。唯一的功夫是把格子編號轉成 蛇行排列的(row, col)。
歸約到：bfs § Template 2 — 邊由骰子算出來，而不是來自鄰接串列。
python
# python
# LC 909 - Snakes and Ladders
# IDEA: BFS over squares; a roll lands on s+1..s+6 and is redirected by a snake or ladder
# time = O(n^2), space = O(n^2) n^2 squares, 6 edges each
from collections import deque
def snakesAndLadders(board):
n = len(board)
def cell(square): # square number -> (row, col) on the board
r, c = divmod(square - 1, n)
row = n - 1 - r # square 1 is bottom-left
col = c if r % 2 == 0 else n - 1 - c # every other row runs right to left
return row, col
target = n * n
queue = deque([1])
moves = {1: 0} # doubles as the visited set
while queue:
square = queue.popleft()
if square == target:
return moves[square]
for nxt in range(square + 1, min(square + 6, target) + 1):
r, c = cell(nxt)
if board[r][c] != -1:
nxt = board[r][c] # take the snake or ladder
if nxt not in moves:
moves[nxt] = moves[square] + 1
queue.append(nxt)
return -1
java
// java
// LC 909 - Snakes and Ladders
// IDEA: flatten the board to squares 1..n*n, then BFS; dice roll = edge
// time = O(n^2), space = O(n^2)
public int snakesAndLadders(int[][] board) {
int n = board.length;
int[] flat = new int[n * n + 1];
int idx = 1; boolean leftToRight = true;
for (int r = n - 1; r >= 0; r--) {
if (leftToRight) for (int c = 0; c < n; c++) flat[idx++] = board[r][c];
else for (int c = n - 1; c >= 0; c--) flat[idx++] = board[r][c];
leftToRight = !leftToRight;
}
boolean[] visited = new boolean[n * n + 1];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{1, 0});
visited[1] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int pos = curr[0], steps = curr[1];
for (int dice = 1; dice <= 6 && pos + dice <= n * n; dice++) {
int next = pos + dice;
if (flat[next] != -1) next = flat[next];
if (next == n * n) return steps + 1;
if (!visited[next]) { visited[next] = true; queue.offer(new int[]{next, steps + 1}); }
}
}
return -1;
}
陷阱
- 要標記的是走完蛇或梯子之後停下來的格子，不是骰子顯示的格子；梯子的起點不是你會停留的地方。
- 每擲一次只走一段蛇或梯子：落在一條梯子的終點、而那裡剛好是另一條梯子的起點，並不會連著走。
相似題 — LC 1971（模板的錨定題） · LC 1306（把 jump game 當成圖）
多源 BFS 的題目
Walls and Gates — LC 286
關鍵 — 「每個房間到最近的門的距離」就是一次 BFS，把每扇門都放在距離 0 當起點。最先抵達 某個房間的門走的是最短路徑，所以房間在第一次入列時就寫好；
INF同時代表「還沒到過」。
歸約到：bfs § Template 4 — 距離直接存在格子裡。
python
# python
# LC 286 - Walls and Gates
# IDEA: seed every gate; the first time BFS reaches an INF room, that distance is final
# time = O(m * n), space = O(m * n)
from collections import deque
def wallsAndGates(rooms):
if not rooms:
return
INF = 2147483647
m, n = len(rooms), len(rooms[0])
queue = deque((r, c) for r in range(m) for c in range(n) if rooms[r][c] == 0)
while queue:
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1 # mark on enqueue = the distance
queue.append((nr, nc))
java
// java
// LC 286 - Walls and Gates
// IDEA: multi-source BFS from all gates; write the distance when a room is first reached
// time = O(m * n), space = O(m * n)
public void wallsAndGates(int[][] rooms) {
int m = rooms.length, n = rooms[0].length;
int INF = Integer.MAX_VALUE;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (rooms[i][j] == 0) queue.offer(new int[]{i, j});
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
rooms[nr][nc] = rooms[cell[0]][cell[1]] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
}
陷阱
- 每扇門各跑一次 BFS 再取最小值是對的，但慢了 k 倍。
- 牆是
-1，永遠不是INF，所以== INF的判斷已經跳過牆和每一扇門。
相似題 — LC 542（最近的 0，在 bfs § Template 4 解） · LC 1162 · LC 994
Surrounded Regions — LC 130
關鍵 — 把問題反過來。一個
'O'會留下來，若且唯若它和邊界上的某個'O'相連，所以用每個 邊界'O'當 BFS 起點，把走得到的都標成安全，再把沒走到的'O'全部翻掉。
歸約到：bfs § Template 4 — 起點是邊界上的格子，而且只保留可達性。
python
# python
# LC 130 - Surrounded Regions
# IDEA: BFS inward from every border 'O' marking 'S'; then O -> X (captured) and S -> O (safe)
# time = O(m * n), space = O(m * n)
from collections import deque
def solve(board):
if not board:
return
m, n = len(board), len(board[0])
queue = deque()
for r in range(m):
for c in range(n):
if (r in (0, m - 1) or c in (0, n - 1)) and board[r][c] == 'O':
board[r][c] = 'S' # safe: touches the border
queue.append((r, c))
while queue:
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'O':
board[nr][nc] = 'S'
queue.append((nr, nc))
for r in range(m):
for c in range(n):
if board[r][c] == 'O':
board[r][c] = 'X' # never reached from the border: captured
elif board[r][c] == 'S':
board[r][c] = 'O'
java
// java
// LC 130 - Surrounded Regions
// IDEA: BFS from border O-cells to find the regions that are not surrounded
// time = O(m * n), space = O(m * n)
public void solve(char[][] board) {
int m = board.length, n = board[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
board[i][j] = 'S'; queue.offer(new int[]{i, j});
}
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!queue.isEmpty()) {
int[] c = queue.poll();
for (int[] d : dirs) {
int nr = c[0] + d[0], nc = c[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O') {
board[nr][nc] = 'S'; queue.offer(new int[]{nr, nc});
}
}
}
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
board[i][j] = board[i][j] == 'S' ? 'O' : (board[i][j] == 'O' ? 'X' : board[i][j]);
}
陷阱
- 對每個內部區域做 flood fill 再檢查有沒有碰到邊界也行，但猜錯的區域要復原；從邊界出發就不用猜。
- 需要第三種標記（
'S'）：把連到邊界的格子直接翻回'O'，會和還沒走訪的格子分不出來。
相似題 — LC 1020 Number of Enclaves · LC 1254（DFS 寫法，dfs § Template 7） · LC 417
即時產生鄰居的 BFS 題目
Open the Lock — LC 752
關鍵 — 每個 4 位數組合是一個節點，鄰居是轉動一個轉輪一格得到的 8 個組合，需要時才產生。 deadend 是從圖上拿掉的節點。BFS 的層數就是轉動次數，所以目標第一次被彈出時就是最小值。
歸約到：bfs § Template 5 — 字母表是 10 個數字，每個位置可以往兩個方向轉。
python
# python
# LC 752 - Open the Lock
# IDEA: BFS over combinations; neighbours = turn one wheel +1 or -1 (mod 10), skipping deadends
# time = O(10^4 * 8), space = O(10^4) at most 10^4 states, 8 neighbours each
from collections import deque
def openLock(deadends, target):
dead = set(deadends)
if "0000" in dead:
return -1
queue = deque(["0000"])
seen = {"0000"}
turns = 0
while queue:
for _ in range(len(queue)):
code = queue.popleft()
if code == target:
return turns
for i in range(4):
digit = int(code[i])
for step in (1, -1):
nxt = code[:i] + str((digit + step) % 10) + code[i + 1:]
if nxt not in seen and nxt not in dead:
seen.add(nxt)
queue.append(nxt)
turns += 1
return -1
java
// java
// LC 752 - Open the Lock
// IDEA: BFS on 4-digit combinations; each turn = 1 step
// time = O(10^4 * 8), space = O(10^4)
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
String start = "0000";
if (dead.contains(start)) return -1;
queue.offer(start);
visited.add(start);
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curr = queue.poll();
if (curr.equals(target)) return steps;
char[] chars = curr.toCharArray();
for (int j = 0; j < 4; j++) {
char orig = chars[j];
for (int delta : new int[]{1, -1}) {
chars[j] = (char) ((orig - '0' + delta + 10) % 10 + '0');
String next = new String(chars);
if (!visited.contains(next) && !dead.contains(next)) {
visited.add(next); queue.offer(next);
}
chars[j] = orig; // restore before the next wheel
}
}
}
steps++;
}
return -1;
}
陷阱
"0000"本身可能就是 deadend：在 BFS 開始前就回傳 -1。(digit - 1) % 10在 Python 是9，在 Java 是-1；Java 需要+ 10。
相似題 — LC 127（錨定題） · LC 433 Minimum Genetic Mutation · LC 773
Perfect Squares — LC 279
關鍵 — 把每個剩餘的數當節點，「減掉一個完全平方數」當邊。加總為
n的最少平方數個數，就是 從n到 0 的最少邊數，所以從n出發的 BFS 回傳某次相減第一次碰到 0 的那一層。
歸約到：bfs § Template 5 — 鄰居是 remaining - k²。
python
# python
# LC 279 - Perfect Squares
# IDEA: BFS from n; one level = one more square used; the first subtraction that reaches 0 wins
# time = O(n * sqrt(n)), space = O(n) each amount is enqueued once, sqrt(n) squares tried
from collections import deque
def numSquares(n):
squares = []
i = 1
while i * i <= n:
squares.append(i * i)
i += 1
queue = deque([n])
seen = {n}
count = 0
while queue:
count += 1 # squares used by the amounts generated this level
for _ in range(len(queue)):
remaining = queue.popleft()
for sq in squares:
left = remaining - sq
if left == 0:
return count
if left < 0:
break # squares are ascending: the rest are larger
if left not in seen:
seen.add(left)
queue.append(left)
return count
陷阱
- 沒有
seen，同一個數會被很多種順序走到（12 - 4 - 1與12 - 1 - 4），佇列會爆掉。 - DP
dp[i] = 1 + min(dp[i - k²])有同樣的上界，也是面試官期待的另一種答案；BFS 可以提早結束，DP 不行。
相似題 — LC 322 Coin Change（同一張圖，硬幣有權重） · LC 127
Sliding Puzzle — LC 773
關鍵 — 和 LC 752 同一個骨架；只有狀態編碼和鄰居規則不同。把 2×3 的盤面攤平成像
"123450"的字串，並預先算好空格可以和哪些索引交換，這樣產生鄰居就是查表，而不是做邊界檢查。720 種排列 只有一半走得到，所以-1是真的會出現的答案。
歸約到：bfs § Template 5 — 狀態是整個盤面。
text
index layout swap table (neighbours of each index)
0 1 2 0:[1,3] 1:[0,2,4] 2:[1,5]
3 4 5 3:[0,4] 4:[1,3,5] 5:[2,4]
python
# python
# LC 773 - Sliding Puzzle
# IDEA: BFS on the flattened board string; the blank '0' swaps with its table neighbours
# time = O(6! * 6), space = O(6!) at most 720 board states
from collections import deque
def slidingPuzzle(board):
start = "".join(str(x) for row in board for x in row)
target = "123450"
neighbours = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
queue = deque([start])
seen = {start}
moves = 0
while queue:
for _ in range(len(queue)):
state = queue.popleft()
if state == target:
return moves
zero = state.index('0')
for j in neighbours[zero]:
cells = list(state)
cells[zero], cells[j] = cells[j], cells[zero]
nxt = "".join(cells)
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
moves += 1
return -1 # the target permutation is unreachable
java
// java
// LC 773 - Sliding Puzzle
// IDEA: state = flattened board string; BFS levels = number of moves
// time = O(6! * 6), space = O(6!)
public int slidingPuzzle(int[][] board) {
StringBuilder sb = new StringBuilder();
for (int[] row : board) for (int v : row) sb.append(v);
String start = sb.toString(), target = "123450";
int[][] nbr = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}}; // precomputed adjacency
Queue<String> q = new LinkedList<>();
Set<String> seen = new HashSet<>();
q.offer(start); seen.add(start);
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
if (cur.equals(target)) return steps;
int zero = cur.indexOf('0');
for (int j : nbr[zero]) { // slide a tile into the blank
char[] arr = cur.toCharArray();
char tmp = arr[zero]; arr[zero] = arr[j]; arr[j] = tmp;
String next = new String(arr);
if (seen.add(next)) q.offer(next);
}
}
steps++;
}
return -1;
}
陷阱
- 換成別的盤面形狀時，手寫交換表最容易出錯；盤面不是 2×3 時，從
(r ± 1, c)/(r, c ± 1)推出來。 - 在各個鄰居之間共用同一個 list 做交換（而不是每次複製一份），會弄壞同一個狀態之後的每個鄰居。
相似題 — LC 752 · LC 854 K-Similar Strings
父節點表 + 向外輻射的題目
Closest Leaf in a Binary Tree — LC 742
關鍵 — 把樹轉成無向圖（parent map），從節點
k開始 BFS；第一個彈出的葉節點就是最近的。
歸約到：tree_lca_distance.md § LC 742，完整解在那裡；這裡只是指標。