close

捷徑電路法

有時候會有一張地圖，說某些地方雙向，某些地方單向，求起點到終點的走法數。

 

如果都沒有雙向道的話，這種問題直接用「爬格子」比較快，也就是從起點開始，與起點連接的為1，交會的地方則將兩點數值相加即可。

 

如果有雙向道，則可以試試「捷徑電路法」。就是把非雙向道的部份用二極體(或電阻，只是一個示意符) 取代，然後利用「同點同電位」，把電路縮成「魚」的形狀，就很簡單了。

arrow
arrow
    全站熱搜

    GPhettoH 發表在 痞客邦 留言(0) 人氣()