這篇文章，會帶著大家複習以前學過的DFS框架，
並且以圖論的應用題與概念為核心，貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
DFS 深度優先搜索框架
def dfs( parameter ):
# 邊界條件
if base case or stop condition:
# 更新結果
return
# 通則
for each child node:
# 更新參數，遞回下一層的節點
dfs( updated parameter)
return
如果特化成圖論中N4 四連通探索的DFS，往往具有下列形式
def dfs( parameter ):
if base case or stop condition:
# 更新結果
return
# 更新參數，遞回4連通相鄰的節點
mark current node as visited
# 分別是 左、右、上、下 四個鄰居
dfs( updated parameter, and go left )
dfs( updated parameter, aad go right )
dfs( updated parameter, and go up )
dfs( updated parameter, and go down )
return
示意圖
常見的用途:
深度優先探索，探索整張圖(也可以是樹、鏈結串列。)
檢測是否有滿足特定條件的路徑(存在性的判斷)
Word Search - LeetCode 搜尋特定的單字是否存在
這題給定一個矩陣，問我們這個矩陣中，是否存在一條N4 四連通的路徑，路徑上的字串恰好是某個特定的單字。
剛好就是我們剛剛提到的存在性判斷，檢測是否有滿足特定條件的路徑。
掃描整個矩陣，依序從每個格子點出發，依序拜訪四連通鄰居，一直往下走，看看有沒有一條路徑剛好可以拼出某個特定的單字。
實作上有一個細節要特別留意，為了避免重複搜索造成無窮循環，每個被我們拜訪過的格子點會先暫時標記成"#"代表已經走過，所有路徑都拜訪過之後，才會還原回來。
以DFS +N4探索框架的形式實現演算法，程式碼如下:
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board:
# Quick response for empty board
return False
h, w = len(board), len(board[0])
# ------------------------------------------------------
def dfs_search(idx: int, x: int, y: int) -> bool:
if x < 0 or x == w or y < 0 or y == h or word[idx] != board[y][x]:
# Reject if out of boundary, or current grid cannot match the character word[idx]
return False
if idx == len(word) - 1:
# Accept when we match all characters of word during DFS
return True
cur = board[y][x]
# mark as '#' to avoid repeated traversal
board[y][x] = '#'
# visit next four neighbor grids
found = dfs_search(idx + 1, x + 1, y) or dfs_search(idx + 1, x - 1, y) or dfs_search(idx + 1, x, y + 1) or dfs_search(idx + 1, x, y - 1)
# recover original grid character after DFS is completed
board[y][x] = cur
return found
# ------------------------------------------------------
return any(dfs_search(0, x, y) for y in range(h) for x in range(w))
接著看進階延伸題，改成找辭典裡面的單字，把有找到的列出來。
Word Search II - LeetCode 搜尋給定辭典中的單字
這題多了辭典，我們可以用之前學過前綴樹的技巧，先把辭典建成一顆Trie。
接著，同步在矩陣和Trie裡面搜索每個字元，假如在某一格可以在Trie中找到一個單字，就把這個單字加入到最終結果的清單中。
以DFS +N4探索框架的形式實現演算法，程式碼如下:
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# Build a trie from given words
trie = {}
for word in words:
curr = trie
for c in word:
if c not in curr:
curr[c] = {}
curr = curr[c]
curr['@'] = word
H, W = len(board), len(board[0])
res = []
# ===========================================
def dfs(r, c, trie):
# Skip out-of-board search
if not ( 0 <= r < H ) or not ( 0 <= c < W):
return
# Get current character on board
ch = board[r][c]
# Skip if current character does not exist in Trie
if ch not in trie:
return
curr = trie[ch]
word = curr.pop('@', None)
if word:
# We've found a word matched in Trie
res.append(word)
# Avoid repeated traversal
board[r][c] = '#'
dfs(r-1, c, curr)
dfs(r+1, c, curr)
dfs(r, c-1, curr)
dfs(r, c+1, curr)
board[r][c] = ch
# Deleted empty trie branch
if not curr:
trie.pop(ch)
return
# =========================================
# Scan each position on board
for r in range(H):
for c in range(W):
dfs(r, c, trie)
return res
還有一個類似題，要求我們計算可以從起點走到終點，
而且可以拜訪所有空白格子點的路徑方法數
Unique Paths III - LeetCode 拜訪所有空白格子點的路徑方法數
其實也是類似的，我們可以先計算有幾個空白格子點。
接著從起點開始用DFS+N4拜訪整張棋盤，如果走到終點的時候，恰好拜訪過所有空白格子點，就把方法數累加一。最後的路徑方法數總數就是答案。
以DFS +N4探索框架的形式實現演算法，程式碼如下:
# Define grid state to make it more readable
from collections import namedtuple
GridState = namedtuple('GridState', 'start ending empty obstacle')
grid_state = GridState( start = 1, ending = 2, empty = 0, obstacle = -1)
class Solution:
def uniquePathsIII(self, grid):
h, w = len( grid ), len( grid[0] )
available_grid_count = 0
obstacle_count = 0
src_row, src_col = 0, 0
# record for valid path
# a path is valid if and only if it visits all available grid except for obstacles.
self.valid_path_count = 0
for y in range(h) :
for x in range(w):
if grid[y][x] == grid_state.obstacle:
# update counter of obstacle
obstacle_count += 1
elif grid[y][x] == grid_state.start:
# locate start point
src_row, src_col = y, x
# compute counting of all available grids
available_grid_count = h * w - obstacle_count
# ------------------------------------------------------
def dfs( cur_row, cur_col, depth):
if not ( 0 <= cur_row < h) or not ( 0 <= cur_col < w ):
# Skip out-of-board search
return
if grid[cur_row][cur_col] == grid_state.obstacle:
# Terminate DFS when bumping into an obstacle
return
elif grid[cur_row][cur_col] == grid_state.ending:
if depth == available_grid_count:
# If we reach end with visiting all available grids, update valid path count
self.valid_path_count += 1
# Terminate DFS when reach ending
return
else:
state_backup = grid[cur_row][cur_col]
# mark current grid as obstacle to avoid repeated visit
grid[cur_row][cur_col] = grid_state.obstacle
# DFS + N4 to discover each neighbor cell
dfs( cur_row-1, cur_col, depth + 1)
dfs( cur_row+1, cur_col, depth + 1)
dfs( cur_row, cur_col-1, depth + 1)
dfs( cur_row, cur_col+1, depth + 1)
# restore original grid state
grid[cur_row][cur_col] = state_backup
return
# ------------------------------------------------------
dfs(src_row, src_col, depth = 1)
return self.valid_path_count
結語
好，今天一口氣介紹了最精華的部分，
通用的DFS+N4探索框架，還有相關的路徑應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
