• problem link
  • 題目:感覺跟 TSP 有八成像www

  • 解法: 可以發現大部分的點只有 3 個邊,且只有 16 個點
    暴力枚舉的話約要 \(3^{16} = 43046721\) 個操作
    還行!
    所以就決定很懶惰的暴搜惹

    首先,最困難的部份
    先用力的把圖給打進 code 裡吧 www

    要注意的是有時走回頭路反而更短
    比如這樣的測資

    1
    p o l
    

    若是不回頭的話反而達不到最優解 3
    故暴搜時不需排除已走過的節點

    第一次 AC 時幾乎沒剪枝,跑了 321ms
    第二次用力的剪了一下,居然降到 3ms 惹wwww

  • \(T(n) = O(3^n)\)