藍橋杯「振興中華」跳格子路徑計數：C++ DFS 無限遞歸修正

題目回顧

4×5 格子陣列，從左上角「從」出發，僅能上下左右移動，路徑拼成「從我做起振興華」，求路徑總數。

原始代碼核心缺陷

int dfs(int (*A)[5], int a, int b, int sum) {
    if (sum == 36) res++;
    for (int i=0; i<=1; i++)
        for (int j=0; j<=1; j++)
            if (b<4 && a<3)
                dfs(A, a+i, b+j, sum+A[a+i][b+j]); // i=j=0 時原地遞歸，無限循環
    // 邊界處理邏輯混亂
}

錯誤分析

• 無限遞歸：i=0, j=0 時 dfs(a, b, ...) 原地呼叫自己，無終止條件。
• 移動方向錯誤：題目僅允許上下左右（曼哈頓距離 1），雙層迴圈產生對角線與原地移動。
• 狀態定義不清：sum 累加數值無法對應「振興中華」字符序列。

正確建模

1. 將目標字串「從我做起振興華」拆解為字符陣列 target[]。
2. DFS 狀態：(x, y, idx) 表示當前位置 (x,y) 已匹配至 target[idx]。
3. 四方向嘗試：dx[]={-1,1,0,0}, dy[]={0,0,-1,1}。
4. 邊界與字符匹配檢查：nx,ny 在範圍內且 grid[nx][ny] == target[idx+1]。
5. 遞歸終止：idx == target.length-1 計數器++。

參考代碼框架

char grid[4][5] = {...}; // 對應題目字符
char target[] = "從我做起振興華";
int cnt = 0;
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};

void dfs(int x, int y, int idx) {
    if (idx == strlen(target)-1) { cnt++; return; }
    for (int d=0; d<4; d++) {
        int nx = x+dx[d], ny = y+dy[d];
        if (nx>=0 && nx<4 && ny>=0 && ny<5 && grid[nx][ny] == target[idx+1])
            dfs(nx, ny, idx+1);
    }
}

int main() {
    dfs(0, 0, 0); // 從 grid[0][0]='從' 開始
    printf("%d\n", cnt);
    return 0;
}

答案提交

執行上述程式可得整數答案，直接提交數字即可（無需輸出過程）。