最短経路問題の例をC#で解く

またトップコーダーの問題を挑戦しました。今回のアルゴリズムは原点から目的まで行くためにテレポートを使用できます。順列とタプルを数えてすべての道を計算出来ます。
This problem involves the genres of combinatorics and shortest path search. It runs in O(1152). Basically, the goal is to find the shortest distance traversed on a Cartesian grid between a start (xm,ym) point and a destination (xh,yh) point. The caveat is that three teleports are provided, each of which costs 10 to use and contains {x1 y1 x2 y2} coords for start and end. To complicate matters further, the teleports are bidirectional and can be used in any order (or not at all). Thus, in order to consider all possible ways to travel, you must check all possible numbers of teleports (0,1,2, or 3), all ways to choose that number, all permutations of the teleports chosen, and for each permutation of teleports the binary tuple of directions (1 for (x1,y1) as start, 0 for (x2,y2) as start). Thus, the complexity is O(6*6*4*8) = 1152, as there are 4 numbers of teleports, at most 6 ways to choose each number, at most 6 permutations, and at most binary tuples for any permutation of teleports (i.e. 2^3 for 3).
The algorithm simply checks the total cost for each (num teleports, choice, perm,direction binary tuple) selection and compares this to a minimal cost. The cost of a teleport = distance from curr location to teleport + 10. The cost after all teleports is |xh-xc|+|yh-yc| where (xc,yc) is location after last teleport.