信息學奧賽「產生數」題解：BFS 狀態轉移計算可達數字數量

題目大意

給定初始數字串 (長度 ≤ 32) 與 k 條轉換規則 (k ≤ 15)。規則：一位數字可轉換為另一位非零數字。從初始串每個位置出發，應用規則進行 BFS 擴展，統計每個起始位置能到達的不同數字總數，最終答案為各位置可達數量的乘積。

算法思路

1. 對初始字串每個字符作為 BFS 起點。
2. 隊列存儲當前可達數字，Visited[10] 標記已訪問數字。
3. 對隊列中每個數字，嘗試套用所有規則：若當前數字匹配規則左側且目標數字未訪問，則入隊並標記。
4. 統計該起點可達數字數 temp，累乘到答案 ans。

關鍵代碼片段

for (j = 0; j < len; j++) {
    temp = 1;
    memset(Visited, 0, sizeof(Visited));
    q[++tail] = num[j] - '0';
    do {
        head++;
        for (i = 1; i <= K; i++) {
            if (q[head] == x[i] && Visited[y[i]] == 0) {
                q[++tail] = y[i];
                temp++;
                Visited[x[i]] = Visited[y[i]] = 1;
            }
        }
    } while (head < tail);
    ans *= temp;
}

複雜度分析

• 起點數 ≤ 32，每個 BFS 狀態數 ≤ 10 (數字 0-9)，規則 ≤ 15。
• 總時間 O(len × 10 × K) ≈ 4800 次操作，極快。

注意事項

• 規則右側數字非零，但代碼未顯式檢查，題目保證輸入合法。
• 答案可能很大，需用 long long (64 位)。