在此抄襲借用 Competitive Programming Handbook 的例子。
書中第 62 頁畫了 7x7 格子，求左上走過所有格子到右下的路徑數。
對 dfs 有概念的人應該能輕鬆完成初步的程式，只是會超時，因此下面有幾個優化步驟。
很明顯，每條路都有一條對稱的路徑，
如想讓對稱的路徑不被算到，只需讓第一步往下，最後答案乘 2 即可。
依照題意，終點必須是最後一個走到的，下圖在規則上算明顯的死路。
如果路徑把格子分成兩塊，無論走哪一邊之後都不能到另一邊，
這是比較抽象、需要思考的死路。
書中到這裡就結束了，但其實還有別的辦法，見下圖。
這也是一條行不通的路徑，
在程式中判斷上方和左右是否相隔，便可減少不必要的嘗試。
調整前: 0.418s
調整後: 0.188s
遇到三面環山(周圍只有一格沒走過)的格子必須先走，否則之後走到它就走不出去了。
調整後: 0.084s
終點左上角也分隔兩塊區域，無解。
調整後: 0.788s
改完之後甚至能跑 8x8 的格子，用時 4s，可是卻沒有一條適合的路徑。
實際上，只要 n 是偶數一定無解，原因見下圖。
把每個格子交錯填上 O 和 X，如果你站在 O，下一步一定是 X。
起點終點都在 O，代表路徑頭尾都是 O，也就是路徑長度(=nxn)必為奇數。
字母和數字對應關係只有 10! 種。
枚舉它們再判斷算式是否成立。
枚舉 index i,j，如果他們減幾個 k 後相等，k 一定是 a_i, a_j 之差的因數。
枚舉因數，判斷是否符合題意。
這真的是 1900 分的題目嗎？
iThome鐵人賽
看影片追技術