MediumRating 2186

3377. Digit Operations to Make Two Integers Equal

mathgraphheap-priority-queuenumber-theoryshortest-path

解題說明

Digit Operations to Make Two Integers Equal

題目描述：給定兩個整數 n 和 m，每次操作可以將 n 的某一位數字加 1 或減 1（不能使首位變為 0，也不能使某位從 9 加 1 或從 0 減 1）。每次操作的成本是操作後 n 的值。過程中 n 不能是質數。求將 n 變成 m 的最小成本，若不可能回傳 -1。

解題思路：將每個可能的數值視為圖的節點，相鄰數值（某位數字 ±1）之間有邊，邊權為目標數值。使用 Dijkstra 從 n 出發找到 m 的最短路徑。需要預先用篩法標記所有質數，質數節點不可經過（除非是起點或終點本身為質數也不可使用，需依題意判斷）。由於數字範圍限於與 n 相同位數的整數，狀態空間有限。

C++ 解法

複雜度分析

時間複雜度：O(M log M) — M 為數值範圍（最多 10⁵）。每個節點最多入堆一次，每個節點有 O(D) 個鄰居（D 為位數，最多 5），堆操作 O(log M)。加上篩法 O(M log log M)。

空間複雜度：O(M) — 篩法和距離陣列各使用 O(M) 空間。

虛擬碼

1. Sieve primes up to 99999
2. If n or m is prime, return -1
3. Initialize dist[n] = n, all others = INF
4. Push (n, n) to min-heap
5. While heap is not empty:
   a. Pop (d, u); if u == m, return d
   b. For each digit position i of u:
      For delta in {-1, +1}:
        Compute new number v by changing digit i
        Skip if leading zero or out of range or v is prime
        new_dist = d + v
        If new_dist < dist[v]: update and push
6. Return -1

其他解法

BFS（無權重） O(M)：若成本一致（每步成本為 1），可用 BFS。但此題成本為到達的數值本身（不同），需要 Dijkstra。

A 搜尋*：使用 |n - m| 或數字差距作為啟發式函數，可能加速搜尋但最壞情況不變。需要確保啟發式函數可容納（admissible）。

延伸思考

如果允許同時修改多位數字（一次操作），成本如何定義？問題複雜度如何變化？
如果約束改為不能經過合數（而非質數），問題的可解性如何？
如果 n 和 m 的位數不同（允許增加或刪除位數），問題如何擴展？

Digit Operations to Make Two Integers Equal — CaffeCode