d663 - 11730 - Number Transformation
題目描述
題目要求計算將數字 S 轉換為數字 T 所需的最少步驟數。轉換的規則是，每次可以將當前數字加上其一個質因數。如果無法轉換，則輸出 -1。
解題思路
這題可以建模成一個圖，其中每個數字是一個節點，如果一個數字可以透過加上其質因數轉換到另一個數字，則這兩個節點之間存在一條邊。然後，問題就變成了在圖中找到從 S 到 T 的最短路徑。
程式碼中，s[i][j] 儲存了數字 i 的第 j 個質因數。sdp[st][it] 儲存了從 st 出發到 it 的最小步驟數。sdfs 函數使用深度優先搜尋 (DFS) 進行探索，並更新 sdp 陣列。雖然使用了 DFS，但其核心思想是動態規劃，避免重複計算。
在主函數中，首先預處理出每個數字的質因數，然後使用 DFS 計算所有數字之間的最小步驟數。最後，對於每個測試案例，查詢 sdp[S][T] 的值，如果為初始值 1000，則表示無法到達，輸出 -1，否則輸出 sdp[S][T]。
複雜度分析
- 時間複雜度: O(1000 * 1000 * 質因數數量) 最壞情況下，需要遍歷所有數字，並對每個數字計算其質因數，然後進行 DFS 探索。
- 空間複雜度: O(1000 * 1000) 主要用於儲存
sdp陣列。
程式碼
#include <iostream>
using namespace std;
int s[1005][1005],S,T,ca,sdp[1005][1005];
void sdfs(int it,int st,int v){
if(it>1000)return;
if(sdp[st][it]<=v)return;
sdp[st][it]=v;
for(int i=s[it][0];i>=1;--i){
sdfs(it+s[it][i],st,v+1);
}
}
int main(){
//cin.tie(0); ios::sync_with_stdio(false);
for(int i=1;i<=1000;++i){
int it=1;
for(int j=2;j<=i/2;++j){
if(i%j==0){
int ac=1;
for(int k=2;k<=j/2&∾++k){
if(j%k==0)ac=0;
}
if(ac){
s[i][it]=j;
++it;
}
}
}
s[i][0]=it-1;
}
for(int i=1;i<=1000;++i){
for(int j=1;j<=1000;++j){
sdp[i][j]=1000;
}
sdfs(i,i,0);
}
while(cin >> S >> T){
if(S+T==0)break;
cout << "Case " << ++ca << ": ";
if(sdp[S][T]==1000){
cout << "-1\n";
}
else{
cout << sdp[S][T] << "\n";
}
}
}