題目連結: https://zerojudge.tw/ShowProblem?problemid=d663
# 內容
給你一個數字 S，你可以將 A 轉換成 B 藉由加上一個 X，X 是一個 A 的質因數 (1 跟 A 不考慮進去)，現在你的工作就是找出最少需要轉換次數把 S 轉換成 T
# 解題思路
使用 BFS 將所有 S+X 的狀況都加到佇列內部，並記錄下次數，直到找到 T 為止，記得，如果有記錄過 S+X 狀況的話，就不需要再紀錄一次！！
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
int primes[1050], pointer, S, T, minn, cases, buffer1, buffer2; | |
bool notprime[1050] = { true, true }; | |
void Initialize() { | |
for (int i = 2; i < 1050; i++) { | |
if (!notprime[i]) | |
primes[pointer++] = i; | |
for (int j = 0; i * primes[j] < 1050 && j < pointer; j++) | |
notprime[i * primes[j]] = true; | |
} | |
} | |
int main() { cin.sync_with_stdio(false), cin.tie(0), cout.tie(0); Initialize(); | |
queue <int> BFS, times; | |
while (cin >> S >> T, S || T) { | |
cout << "Case " << ++cases << ": "; | |
if (S == T) cout << "0\n"; | |
else { | |
bool have[1001] = {}; | |
BFS.push(S), times.push(1), have[S] = true, minn = 2147483647; | |
while (!BFS.empty()) { | |
buffer1 = BFS.front(), buffer2 = sqrt(buffer1); | |
for (int i = 0; primes[i] < buffer1; i++) | |
if (!(buffer1 % primes[i])) { | |
buffer2 = buffer1 + primes[i]; | |
if (buffer2 < T && !have[buffer2]) | |
BFS.push(buffer2), times.push(times.front() + 1), have[buffer2] = true; | |
else if (buffer2 == T && times.front() < minn) | |
minn = times.front(); | |
} | |
BFS.pop(), times.pop(); | |
} | |
if (minn == 2147483647) cout << "-1\n"; | |
else cout << minn << '\n'; | |
} | |
} | |
} |
