#15770: 解題方向


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.32.172]
最後登入時間 :
2024-05-01 19:33:23
a562. ITSA201112 P2 小白鼠走方格 -- ITSA201112 | From: [140.113.208.181] | 發表日期 : 2018-10-28 16:29

這一題的做法一開始我看以為是DFS去展開 但是地圖最大是8x8, 這樣會導致展開時間太久

地圖最大是8x8 感覺和狀態壓縮相關但不知道怎麼下手?

但是後來google到 morris1028 大大的程式碼, 有使用Priority Queue 看不太懂想法QQ

想問一下解題的方向和想法, 先感謝其他大大的指點

 
#17951: Re:解題方向


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.32.172]
最後登入時間 :
2024-05-01 19:33:23
a562. ITSA201112 P2 小白鼠走方格 -- ITSA201112 | From: [61.231.66.54] | 發表日期 : 2019-06-05 02:05

隔了一段時間後來想了一下有哪些有效的剪枝條件。

這題的時間限制相對寬鬆,可以用暴力法枚舉每個起點看能走到的最長路徑,若根據上述做法時間大約是7s左右。

問題就在於怎麼提出有效的剪枝條件,後來自己摸索做了一個相對簡單的版本:

(1) 只有當走到路徑盡頭時才做判斷

(2) 當(目前)最佳解出現的時候,紀錄已經拜訪過的地圖狀態,以後枚舉起點時避開處於最佳解的地圖中的點

 

 
 
ZeroJudge Forum