C 語言「馬的移動」最短步數問題：遞歸/動態規劃解法詳解

題目重述（根據圖片推測）

國際象棋「馬」在數軸/棋盤上從位置 N 移動到 K，每步可走：
1) x → x+1 或 x-1（步長 1）
2) x → 2*x（倍增）
求最少步數。（經典「隋唐英雄傳」/「Catch That Cow」/ POJ 3278 / BOJ 1697 變體）

核心思路：BFS 廣度優先搜索（最優解）

狀態空間無權圖，單源最短路徑 → **BFS 保證最少步數**，時間 O(MAX)、空間 O(MAX)。

關鍵代碼 (C/C++)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;

const int MAX = 100000; // 題目範圍上限
int dist[MAX + 1];

int bfs(int n, int k) {
    if (n >= k) return n - k; // 只能 -1 走回去
    memset(dist, -1, sizeof(dist));
    queue q;
    q.push(n);
    dist[n] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        int nx[3] = {x - 1, x + 1, x * 2};
        for (int i = 0; i < 3; i++) {
            int y = nx[i];
            if (y >= 0 && y <= MAX && dist[y] == -1) {
                dist[y] = dist[x] + 1;
                if (y == k) return dist[y];
                q.push(y);
            }
        }
    }
    return -1;
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    printf("%d\n", bfs(N, K));
    return 0;
}

遞歸/DP 替代思路（教學參考）

• 遞歸 + 備忘錄：f(n) = 1 + min(f(n-1), f(n+1), f(n*2))，需處理邊界、循環依賴，**不推薦**（易棧溢出、重複計算）。
• 動態規劃：dp[i] 從 N 到 i 最少步數，但狀態轉移涉及 i/2、i-1、i+1，**拓撲序難確定**，不如 BFS 自然。

關鍵優化點

1. 邊界剪枝：n >= k 直接返回 n-k（只能遞減）。
2. 訪問標記：dist[] 兼作 visited，避免重複入隊。
3. 上界設置：MAX = 100000 或 2*k 足夠，防止 x*2 無限增長。

BFS 是此類「單步轉移、求最短步數」問題的**標準模板**，背熟框架、調整轉移條件、設置邊界，即可解決所有同類題目。