查看: 188|回復: 0

[TIOJ] [BFS]1008 - 量杯問題

[複製鏈接]

該用戶從未簽到

12

主題

23

帖子

180

積分

高一新生

Rank: 2

積分
180
發表於 2014-9-19 08:03:46 | 顯示全部樓層 |閱讀模式

趕快加入我們來參與討論吧!

您需要 登錄 才可以下載或查看,沒有帳號?立即加入

x
原題:http://tioj.ck.tp.edu.tw/problems/1008
測試結果:http://tioj.ck.tp.edu.tw/submissions/2225


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

評分

參與人數 1金幣 +4 收起 理由
Sylveon + 4

查看全部評分

回復

使用道具 檢舉

您需要登錄後才可以回帖 登入 | 立即加入

本版積分規則

快速回覆 返回頂部 返回列表