#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEST 10         // 目標位置
#define MAX_PATH 100    // 單條路徑最大長度
#define MAX_SOLUTIONS 50 // 最多儲存幾組最佳解 (避免記憶體爆掉)

// 全域變數
int best_paths[MAX_SOLUTIONS][MAX_PATH]; // 二維陣列：存多條路徑
int solution_count = 0;                  // 目前找到幾條最佳路徑

// 函式宣告
void line_mover(int, int, int*, int*, int);
void show_path(int*, int);

int main() {
    int path[MAX_PATH];
    int Nlim = 2 * (DEST > 0 ? DEST : -DEST) + 5; // 稍微放寬上限以防DEST太小
    if (Nlim < 10) Nlim = 20; // 基本保護

    // 初始化 moveMax
    int moveMax = Nlim + 1; 
    int *pMax = &moveMax;
    
    printf("Finding all optimal paths to %d...\n", DEST);
    
    line_mover(0, 0, path, pMax, Nlim);

    // 輸出結果
    if (solution_count == 0) {
        printf("No path found.\n");
    } else {
        printf("Found %d optimal path(s) with %d steps:\n", solution_count, *pMax);
        printf("--------------------------------------\n");
        for (int i = 0; i < solution_count; i++) {
            printf("Path %d: ", i + 1);
            show_path(best_paths[i], *pMax);
        }
    }

    return 0;
}

void show_path(int* path, int Nmov) {
    for (int i = 0; i < Nmov; i++) {
        if (path[i] > 0) printf("+%d", path[i]);
        else printf("%d", path[i]);
            
        if (i < Nmov - 1) printf(" -> ");
    }
    printf("\n");
}

void line_mover(int pos, int Nmov, int* path, int* moveMax, int Nlim) {
    
    // 檢查是否到達目的地
    if (pos == DEST) {
        // 情況 A：找到「更短」的路徑
        if (Nmov < *moveMax) {
            *moveMax = Nmov;     // 更新最短步數
            solution_count = 0;  // 清空之前找到的"較長"路徑
            
            // 存入這條新的最短路徑
            memcpy(best_paths[solution_count], path, sizeof(int) * Nmov);
            solution_count = 1;
        }
        // 情況 B：找到「長度相同」的另一條路徑
        else if (Nmov == *moveMax) {
            if (solution_count < MAX_SOLUTIONS) {
                memcpy(best_paths[solution_count], path, sizeof(int) * Nmov);
                solution_count++;
            }
        }
        return; 
    }

    // 剪枝與遞迴
    // 注意：這裡必須是 Nmov < *moveMax，
    // 因為如果 Nmov 已經等於 *moveMax，再走一步(Nmov+1)絕對會比最佳解長，所以不走。
    if (Nmov + 1 < Nlim && Nmov < *moveMax) {
        Nmov += 1; 
        
        // 向左
        path[Nmov - 1] = -Nmov;
        line_mover(pos - Nmov, Nmov, path, moveMax, Nlim);
        
        // 向右
        path[Nmov - 1] = Nmov;
        line_mover(pos + Nmov, Nmov, path, moveMax, Nlim);
    }
}