藍橋杯 C/C++ A組「振興中華」路徑計數：遞歸回溯全路徑枚舉

第四屆藍橋杯真題：4×5 格子跳躍路徑計數與輸出

從左上角「從」字出發，橫向/縱向移動到相鄰格子，路徑拼成「從我做起振興中華」（8字），求總路徑數、全路徑輸出、指定路徑輸出。

問題建模

• 網格 4 行 × 5 列，字符映射為數字 0~7
• array[4][5] = {{0,1,2,3,4},{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7}}
• 移動規則：右/下，目標值 = 當前值 + 1
• 終點：值為 7（華）

遞歸回溯算法

int count = 0;
int flag[4][5] = {0};      // 路徑標記
int road_flag[7] = {0};    // 步向標記：1=右, 2=下
int step = 0;

void dfs(int r, int c) {
    flag[r][c] = 1;
    if (array[r][c] == 7) {           // 到達終點
        count++;
        // 可選：輸出特定路徑模式
        if (road_flag[0]==1 && road_flag[1]==2 && road_flag[2]==2 &&
            road_flag[3]==2 && road_flag[4]==1 && road_flag[5]==1 && road_flag[6]==1) {
            printPath();              // 輸出 # 表示路徑
        }
        return;
    }
    // 向右
    if (c+1<5 && array[r][c+1]==array[r][c]+1) {
        road_flag[step++] = 1;
        dfs(r, c+1);
        flag[r][c+1] = 0; step--; road_flag[step]=0;  // 回溯恢復
    }
    // 向下
    if (r+1<4 && array[r+1][c]==array[r][c]+1) {
        road_flag[step++] = 2;
        dfs(r+1, c);
        flag[r+1][c] = 0; step--; road_flag[step]=0;
    }
}

運行結果

• 總路徑數：35 條
• 特定路徑：右→下→下→下→右→右→右（對應「從→我↓做↓起↓振→興→中→華」）
• 全路徑輸出：註釋掉特定判斷，在終點直接打印路徑圖

關鍵技術點

1. 狀態標記：flag 防止重複訪問（本題單向遞增天然無環，但通用性需保留）
2. 路徑記錄：road_flag 記錄每步方向，支持模式匹配
3. 回溯恢復：遞歸返回後必須清除標記，否則污染其他分支
4. 邊界檢查：數組越界保護

輸出示例

# ^ ^ ^ ^
^ # ^ ^ ^
^ # ^ ^ ^
^ # # # #   ← 特定路徑可視化

複雜度分析

• 狀態空間：每格最多 2 個出邊，深度固定 7 步
• 時間：O(路徑總數) = 35，極快
• 空間：O(網格大小) = 20