查看: 298|回復: 0

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

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-2-12 11:21
  • 簽到天數: 2 天

    [LV.1]初來乍到

    18

    主題

    31

    帖子

    211

    積分

    好好學生

    Rank: 3Rank: 3

    積分
    211
    發表於 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

    查看全部評分

    回復

    使用道具 檢舉

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

    本版積分規則

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