解題說明
Unique Paths III
題目描述：在一個 m × n 的網格上，每個格子有以下四種狀態之一：
1：起始格（恰好一個）2：結束格（恰好一個）0：空格，可以走-1：障礙，不可走
從起始格出發，走到結束格，路徑必須恰好經過所有空格（含起始格）各一次。回傳所有滿足條件的不同路徑數量。
解題思路：使用回溯法 + 位元遮罩。先掃描網格，記錄起點位置和所有「需要走過」的格子（空格 + 起始格）的總數 need，並將所有可走格子的位置編碼成位元遮罩 all_mask。
用 visited 位元遮罩追蹤已走過的格子。從起點出發，四個方向（上下左右）遞迴探索；當走到終點且 visited == all_mask（所有非障礙格子恰好各走一次），計數加一。位元遮罩使格子的已訪問狀態在 O(1) 時間內查詢和更新，並可搭配記憶化（以 (r, c, visited) 為 key）避免重複計算。
C++ 解法
複雜度分析
時間複雜度：O(4^(m×n))——最壞情況下每個格子有 4 個方向可走，路徑長度最多 m×n，故上界為 4^(m×n)。實際因障礙、已訪問限制和 Hamiltonian path 的稀疏性，遠小於此。若加記憶化（狀態為 (r, c, visited)），上界為 O(m × n × 2^(mn))。
空間複雜度：O(m×n)——遞迴深度最多 m×n（每格走一次），visited 位元遮罩佔 O(1)。若加記憶化則需 O(m × n × 2^(mn)) 空間。
虛擬碼
1. Scan grid: record start position (start_r, start_c) and compute all_mask (bitmask of all non-(-1) cells).
2. Call backtrack(start_r, start_c, visited = 1 << start_cell_id, all_mask).
3. In backtrack(r, c, visited, all_mask):
a. If grid[r][c] == 2 (end cell):
- If visited == all_mask: increment count.
- Return (do not move past end).
b. For each direction (up, down, left, right):
- Compute (nr, nc). Skip if out of bounds or obstacle.
- bit = 1 << (nr * n + nc).
- If bit is set in visited: skip.
- Recurse: backtrack(nr, nc, visited | bit, all_mask).
4. Return count.其他解法
方法一：記憶化搜尋（Bitmask DP）
以 (r, c, visited) 為狀態做記憶化，dp[r][c][visited] 儲存從當前位置出發、已訪問 visited 的路徑數。由於 visited 已知，(r, c) 其實可由 visited 部分推導，但保留 (r, c) 可減少歧義。狀態數 O(m × n × 2^(mn))，適合重複子問題多的情況（本題由於 Hamiltonian path 的特性，重複較少，記憶化提升有限）。
方法二：迭代式 Bitmask DP
dp[mask] 表示「已訪問集合為 mask 且當前在某格子時的路徑方案」——需額外追蹤當前位置。可用 dp[mask][r][c] 表示到達 (r,c) 且訪問集合為 mask 的路徑數，Bottom-up 從起點擴展。時間 O(m × n × 2^(mn))，空間同，但迭代實作無遞迴 stack 開銷。
方法三：輪廓 DP（Profile DP） 若網格為矩形且較窄，可用「逐行」的 DP，每行的狀態以前一行的覆蓋輪廓表示。適合 Hamiltonian path / Hamiltonian cycle 計數的特化情況，實作非常複雜，僅在競程中出現。
延伸思考
- 若路徑不需要恰好覆蓋所有空格，只需從起點走到終點（即 LC 62 Unique Paths 變體），問題難度如何下降？BFS 是否足夠？
- 若網格更大（如 20 × 20），現有的回溯法和位元遮罩都不可行，有哪些近似算法或啟發式方法可以估計路徑數？
- 若允許同一格走多次（但仍需最終恰好走
need步抵達終點），問題轉變為計算「固定步數的自我迴避遊走」，有哪些數學工具可以應用？