POJ 1302 Blue Gene, Jr.：遞歸模擬病毒基因突變規則

問題描述

給定長度 N (≤20) 的字母數字串（大寫字母 A-Z 或數字 0-9），按規則反覆突變直到穩定：

1. 當前段首字符為字母：突變為其右側段發生突變的總次數（取模 10），若無右側段則為 0。
2. 當前段首字符為數字 1-9：自身變為 n-1，並觸發其右側第 n 個字符開始的段突變；若不足 n 個字符，則觸發緊鄰右側段。
3. 當前段首字符為 0：穩定，不再突變。
4. 「右側段」定義：從下一字符開始到串末尾。

輸出最終穩定後的字符串。

遞歸函數設計

int mutate(int pos) 返回從 pos 開始的段總突變次數，並原地修改字符串。

int mutate(int pos) {
    if (pos >= n || s[pos] == '0') return 0;
    if (isalpha(s[pos])) {           // 字母
        int cnt = mutate(pos + 1);
        s[pos] = '0' + (cnt > 9 ? cnt % 10 : cnt);
        return 1 + cnt;
    }
    // 數字 1-9
    int step = s[pos] - '0';
    int cnt;
    if (pos + step < n) cnt = mutate(pos + step);
    else cnt = mutate(pos + 1);
    s[pos]--;  // 變為 n-1
    return 1 + cnt;
}

完整程序

#include 
#include 
#include 

int n;
char s[21];

int mutate(int pos) {
    if (pos >= n || s[pos] == '0') return 0;
    if (isalpha(s[pos])) {
        int cnt = mutate(pos + 1);
        s[pos] = '0' + (cnt > 9 ? cnt % 10 : cnt);
        return 1 + cnt;
    }
    int step = s[pos] - '0';
    int cnt = (pos + step < n) ? mutate(pos + step) : mutate(pos + 1);
    s[pos]--;
    return 1 + cnt;
}

int main() {
    char cmd[20];
    while (scanf("%s", cmd) == 1) {
        if (strcmp(cmd, "ENDOFINPUT") == 0) break;
        scanf("%d\n", &n);
        scanf("%s", s);
        scanf("%s", cmd);  // 讀掉 "END"
        mutate(0);
        printf("%s\n", s);
    }
    return 0;
}

樣例追蹤

輸入 START 4 / A1B2 / END：

1. pos=0 'A' → 字母，遞歸 pos=1
2. pos=1 '1' → 數字1，自身變'0'，觸發 pos=2
3. pos=2 'B' → 字母，遞歸 pos=3
4. pos=3 '2' → 數字2，自身變'1'，觸發 pos=5(越界)→pos=4(越界) 返回0
5. 回溯：pos=3 返回1，pos=2 字母 cnt=1 → 變'1' 返回2，pos=1 返回3，pos=0 字母 cnt=3 → 變'3' 返回4
6. 最終串 3011，匹配樣例輸出。

複雜度與陷阱

• N ≤ 20，遞歸深度極小，無性能問題。
• 注意 pos + step < n 判斷邊界，越界則退回 pos+1。
• 字母突變計數取模 10，數字直接減 1（ASCII 碼連續）。
• 輸入格式含 START N、END、ENDOFINPUT 多行，需仔細讀取換行符。