マークなしが一致、|が追加で、^が削除ってこと？

http://codepad.org/AwwMGCx0 のコードで既に
最短距離の場合のグラフ上の移動方向も分かっている。
そこからゴールからスタートにつながる経路を判定できる。
その経路上で、下に移動=削除、左に移動=追加、斜めに移動=一致と読み替えれば2は出せる。