對SPOJ POUR1的建議？

我需要此問題的幫助POUR1。我認爲它可以用暴力方法來解決，但我讀到它是一個圖形問題（BFS）。我解決了像ABCPATH，LABYR1，PT07Y，PT07Z，BITMAP，...
問題，但我不知道如何以BFS方式處理POUR1。對SPOJ POUR1的建議？

有人可以給我一些建議嗎？

問題陳述：

給定兩個容器，其中一個可容納一升的水，而另一個 - 的水溶液B升，確定的，以獲得在一個水恰好Ç升所需的步驟數的船隻。

在開始時，兩艘船都是空的。以下操作被計數爲「步驟」：

排空的容器中，
填充的容器中，
澆注水從一個容器到另一個，而不溢出，直至容器中的一個或者是全或空。

輸入：

整數t，1 < =噸< = 100，表示測試用例的數量，接着爲T輸入數據集合，每個由三個正整數A，B， c，不大於40000，分成幾行。

輸出：

對於每一組輸入數據，輸出的最小數量的，得到C升所需的步驟，或者爲-1，如果這是不可能的。

實施例：

樣品輸入：

示例輸出：

2 
-1

來源

2013-07-25 user2555240

考慮集中的所有先驗候選條件的狀態（例如[3,7]意思是Vessel1包含3個垃圾，而Vessel2包含7個垃圾）。你有一個有向圖，其頂點是那些狀態，其邊緣是可能的移動。問題是要在圖形中將狀態[0，0]連接到[c，？]類型的狀態或[？，c]類型的狀態。這種路徑通常由BFS搜索。

來源

2013-07-25 22:07:29 hivert

注意，每當一個容器是部分滿，另一個是完全空的或完全充滿，從而降低狀態的總數量。還要注意，對於這個問題，對於容器大小爲'a'和'b'的BFS將花費時間'O（a + b）'，但對於這個問題，應該可能使用'O（log a + log b）'解決方案，使用模塊化逆 –

此問題有一個更簡單的解決方案。不需要BFS。臨時會很好。方法1-填充A，每當A變空時將其清空到B中，只要B變滿就將其填滿。（以上提到的所有動作均視爲個人動作）。繼續這個過程，直到你到達任何一個容器中所需的水量。在這裏獲取移動次數。（比如C1）。方法2-填B，每當B變滿時將它清空爲A，只要A變滿就將其填滿。繼續下去，直到達到所需的金額。獲取C2的移動次數）。答案是min（C1，C2）。在C++ 源代碼：

#include<cstdio> 
#include<algorithm> 
using namespace std; 
int pour(int A,int B,int C){ 
int move=1,a=A,b=0,tfr; 
while(a!=C && b!=C){ 
      tfr=min(a,B-b); 
      b+=tfr; 
      a-=tfr; 
      move++; 
      if(a==C || b==C) 
        break; 
      if(a==0){ 
        a=A; 
        move++; 
      } 
      if(b==B){ 
       b=0; 
       move++; 
      } 
    } 
    return move; 
} 
int gcd(int a,int b){ 
    if(b==0) 
     return a; 
    return gcd(b,a%b); 
} 
int main(){ 
int t,a,b,c; 
scanf("%d",&t); 
while(t--){ 
      scanf("%d%d%d",&a,&b,&c); 
      if(c>a && c>b) 
        printf("-1\n"); 
      else if(c%gcd(a,b) != 0) 
       printf("-1\n"); 
      else if(c==a || c==b) 
       printf("1\n"); 
      else 
       printf("%d\n",min(pour(a,b,c),pour(b,a,c))); 
} 
return 0; 
}

來源

2013-10-21 17:03:26 harunrashid

你能解釋一下計算gcd的原因嗎？ – bornfree

對SPOJ POUR1的建議？

回答

相關問題