Word Search網格回溯
在網格上 DFS 並回復標記。
用在：文字遊戲、迷宮路徑列舉
01為什麼需要它
Boggle 這類遊戲給一盤字母，玩家提交一個字，系統要判斷它能不能由相鄰的格子連出來，而且每格只能用一次。
為什麼用它從每個字母相同的格子出發，往上下左右延伸比對下一個字母，走過的格子先標記起來，這條路走不通就取消標記換另一條。這就是網格上的回溯，「回復標記」讓別條路徑還能經過同一格。
遊戲關卡設計師想知道從入口到出口有幾條不重複經過同一格的路，好判斷關卡是不是太簡單。
為什麼用它BFS 只能找最短的一條，要列出全部就得 DFS 加回溯：每走一格標記，到終點就記錄一條路徑，退回來時取消標記。標記不回復，第二條路就找不到了。
手臂要從初始姿態經過一連串動作到達目標，每一步只能做四種動作之一，有些中間姿態是禁止的。要列出所有合法的動作序列。
為什麼用它姿態是格子、動作是四個方向、禁止姿態是牆，問題形狀和網格回溯一模一樣。網格只是最容易畫出來的狀態空間，同樣的程式套在任何「狀態加轉移」的問題上。
看到這些關鍵字就想到它：網格、相鄰格子、每格只能用一次、找一條路徑或所有路徑、走過要標記、上下左右四個方向、走不通就回頭。
02核心概念
網格回溯把回溯的「選擇」變成往哪個方向走。從一個起點開始，比對目前格子的字母是不是 word[i]，對的話往四個鄰格找 word[i+1]，任一方向成功就整體成功。它和圖的 DFS 是同一件事，差別在 visited 的處理：DFS 找連通分量時走過就永遠不再進，網格回溯卻要在退回時取消標記，因為同一格可以出現在不同的路徑裡，只是不能在同一條路徑裡出現兩次。
標記最省的做法是直接改棋盤：進入格子時把字母改成 #，離開時改回來。因為 # 不等於任何字母，「已走過」的檢查和「字母不對」的檢查合併成同一行 board[r][c] != word[i]。不想動輸入就另外開一個 visited 陣列，邏輯一樣。
三步依然是做選擇（標記）、遞迴（四個方向）、撤銷選擇（回復標記）。這裡的剪枝是「字母不對就立刻 return」，比對發生在進入格子的瞬間，不對的分支連四個方向都不會展開。常見的加速還有：先數一遍棋盤裡各字母的數量，word 需要的字母不夠就直接 false；如果 word 開頭的字母在棋盤裡比結尾的多，反過來搜尋，起點會少很多。
複雜度：m×n 個起點，每個起點最多走 L 層（L 是單字長度），每層 4 個方向（不走回頭路是 3 個），上界 O(m·n·4ᴸ)。空間是遞迴深度 O(L)。要在同一盤棋上找很多個單字（Word Search II），不要一個一個找，把所有單字放進 Trie，DFS 時沿 Trie 走，一次搜尋同時比對所有單字。
03演算法步驟
- 1對棋盤每一格 (r, c) 呼叫
dfs(r, c, 0)，任一個回傳 true 就是找到。 - 2在
dfs(r, c, i)裡先剪枝：出界或board[r][c] != word[i]就 return false。 - 3若
i == len(word) - 1，最後一個字母也對上，return true。 - 4做選擇：把
board[r][c]改成#，對上、右、下、左四個鄰格遞迴dfs(nr, nc, i + 1)，任一個 true 就往上回傳 true。 - 5撤銷選擇：不論結果如何，離開前把
board[r][c]改回原字母。找到時也要復原，別把棋盤留成髒的。
04互動示範
3×4 的網格裡找「SEE」。從左上開始掃起點，遇到 S 就往四個方向探。留意第一個 S 的三個方向都不通後回復標記，以及從第二個 S 出發時，走上面的 E 是死路、回復後才走下面的 E 成功。
實色框是路徑上已標記的格子（角落數字是第幾步），黃色是正在探的鄰格，虛線框是剛回復標記的格子。
05程式碼
Word Search 的原地標記版本，以及列出迷宮所有路徑的變形（用 visited 陣列，到終點不 return 而是記錄後繼續）。
# Word Search（LeetCode 79）：網格上 DFS，走過的格子暫時改成 '#'，回來時改回去
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if board[r][c] != word[i]: # 這格字母不對
return False
if i == len(word) - 1: # 最後一個字母也對上了
return True
ch = board[r][c]
board[r][c] = "#" # 做選擇：標記為已走過
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
board[r][c] = ch # 找到了也要復原，別把棋盤留成髒的
return True
board[r][c] = ch # 撤銷選擇：回復標記
return False
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
# 變形：列出迷宮裡從起點到終點的所有路徑（0 可走、1 是牆）
def all_paths(maze, start, goal):
rows, cols = len(maze), len(maze[0])
ans = []
path = []
visited = [[False] * cols for _ in range(rows)]
def dfs(r, c):
path.append((r, c))
visited[r][c] = True
if (r, c) == goal:
ans.append(path[:])
else:
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == 0 and not visited[nr][nc]:
dfs(nr, nc)
visited[r][c] = False # 回復標記：別條路徑還能經過這格
path.pop()
dfs(*start)
return ans
if __name__ == "__main__":
board = [list("ABCE"), list("SFCS"), list("ADEE")]
print(exist(board, "SEE"), exist(board, "ABCCED"), exist(board, "ABCB")) # True True False
maze = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(len(all_paths(maze, (0, 0), (2, 2)))) # 206練習題
- LeetCode 79Word SearchMedium
- LeetCode 1219Path with Maximum Gold（每條路徑走完都要回復標記）Medium
- LeetCode 130Surrounded Regions（DFS 但不回復標記，比較差別）Medium
- LeetCode 212Word Search II（配合 Trie）Hard
- LeetCode 980Unique Paths III（列出所有走遍空格的路徑）Hard
- LeetCode 2328Number of Increasing Paths in a Grid（嚴格遞增不會走回頭路，不必標記，改用記憶化）Hard