竹園論壇

標題: [BFS]1008 - 量杯問題 [打印本頁]

作者: Shaymin 時間: 2014-9-19 08:03
標題: [BFS]1008 - 量杯問題
原題：http://tioj.ck.tp.edu.tw/problems/1008
測試結果：http://tioj.ck.tp.edu.tw/submissions/2225

經典的隱式圖問題，可以使用BFS來找到滿足狀態的最短路徑(步驟數)，在這裡我們把水杯裡的水量當作狀態，因為這是一個陣列，在這一篇code中，使用最新的C++11 unordered_set加上自訂一hash函數來做處理是否已經使用過的部分。
此外在本題要先把不可能的狀態先剪掉，如目標容量是否大於所有水杯容量，或者是目標容量是不是滿水容量最大公因數的倍數等等，不然會TLE，真的好討厭歐。

歡迎光臨竹園論壇 (http://forum.tfcis.org/)