e527 - 106 彰雲嘉區複賽 - Q7 無刻度容器倒水問題
題目描述
題目要求找出使用兩個無刻度容器，容量分別為 x 和 y，量出 z 升水所需的最少步驟數。步驟包括將容器裝滿、倒空或將一個容器的水倒入另一個容器。如果無法量出 z 升水，則輸出 -1。
解題思路
本題可以使用深度優先搜尋 (DFS) 來解決。狀態空間由兩個容器中的水量表示，即 (x, y)。每次 DFS 嘗試所有可能的動作：
- 將 x 容器裝滿。
- 將 y 容器裝滿。
- 將 x 容器倒空。
- 將 y 容器倒空。
- 將 x 容器的水倒入 y 容器，直到 y 容器滿或 x 容器空。
- 將 y 容器的水倒入 x 容器，直到 x 容器滿或 y 容器空。
DFS 從初始狀態 (0, 0) 開始，並記錄每個狀態的步驟數。如果找到一個狀態，其中一個容器中的水量等於 z，則更新最小步驟數。為了避免無限循環，我們使用一個 visited 陣列來記錄已經訪問過的狀態。
複雜度分析
- 時間複雜度: O(x * y * (x + y))。最壞情況下，DFS 可能需要訪問所有可能的狀態，狀態數量為 x * y。每次 DFS 呼叫需要 O(x + y) 的時間來執行所有可能的動作。
- 空間複雜度: O(x * y)。visited 陣列的大小為 x * y，用於儲存已訪問的狀態。遞迴深度最壞情況下為 x + y。
程式碼
#include <bits/stdc++.h>
using namespace std;
int t,xx,yy,z,a[1026][1026],ans;
void dfs(int x,int y,int ct){
if(a[x][y]<=ct||ct>=ans)return;
a[x][y]=ct;
if(x==z||y==z){
ans=ct;
return;
}
if(x)dfs(0,y,ct+1);
if(y)dfs(x,0,ct+1);
if(x!=xx){
dfs(xx,y,ct+1);
if(y){
if(x+y>xx){
dfs(xx,y-xx+x,ct+1);
}
else{
dfs(x+y,0,ct+1);
}
}
}
if(y!=yy){
dfs(x,yy,ct+1);
if(x){
if(x+y>yy){
dfs(x-yy+y,yy,ct+1);
}
else{
dfs(0,x+y,ct+1);
}
}
}
}
int main(){
cin >> t;
while(t--){
ans=1001;
cin >> xx >> yy >> z;
memset(a,0x3f,sizeof(a));
dfs(xx,yy,0);
if(ans>1000)
cout << "-1\n";
else
cout << ans << "\n";
}
}