機器人初始能量 x，在地圖中移動（上下左右），每步消耗 1 能量。G 點可充滿能量，Y 點需全部走遍。牆 D 不可通行。求最小初始能量 x 使能走完所有 Y。G+Y ≤ 15，地圖 ≤ 15×15。
F(起點)、所有 Y、所有 G 作為關鍵點，編號 0..K-1 (K ≤ 16)。dist[i][j]。若不可達則標記 -1。dp[mask][i] = 走過關鍵點集合 mask，當前在點 i，剩餘能量的最大值。初始 dp[1<。
- 轉移：從
i 走到未訪問的 j，需 dist[i][j] ≤ 當前能量。新能量 = 當前能量 - dist[i][j]；若 j 是 G 則充滿 = x。
- 目標：存在
mask 包含所有 Y 且 dp[mask][*] ≥ 0。
x ∈ [1, 225] (最大步數 15×15)，二分最小可行 x。bool check(int x) {
memset(dp, -1, sizeof(dp));
dp[1<= 0) {
if ((mask & allY) == allY) return true; // 所有 Y 已訪問
for (int j = 0; j < K; ++j) if (!(mask & (1<
複雜度
- BFS：
K * O(n*m) ≤ 16 * 225。
- DP 狀態數：
2^K * K ≤ 65536 * 16 ≈ 1e6。
- 二分
log(225) ≈ 8 次，總計 ~8e6 操作，極快。
總結
經典「關鍵點 + 狀態壓縮 DP + 二分」模式。關鍵點較少 (≤15) 時狀態壓縮可行，BFS 求實際最短路，二分將決策問題轉化為可行性判定。
