一般的な解法
まず、この問題の一般的な解法は、01-BFS になります。
方向転換を考慮する必要があるので、座標 (x, y) + 方向（上下方向 or 左右方向）をノードとします。たとえば、
・(1, 1, '|') : 座標 (1, 1) を上下方向に移動中
・(1, 1, '-') : 座標 (1, 1) を左右方向に移動中
という感じです。そして、これらのノードをリンクで結合します。
座標を変えずに方向だけ変えるリンクを重み 1 とします。
・(1, 1, '|') <----> (1, 1, '-') : 重み 1
ただし、スタートとゴール地点での方向転換は重み 0 にします。（スタート地点での方向転換は自由なので。）
今向いている方向への移動を表すリンクを重み 0 とします。
・(1, 1, '|') <----> (1, 2, '|') : 重み 0
・(1, 1, '-') <----> (2, 1, '-') : 重み 0
あとは、これらで構成される無向グラフについて、スタートからゴールの最小距離を検索します。（スタートとゴールでの方向は任意の方向を1つ決めればOK。スタートとゴール地点の方向転換は重み 0 に注意してください。）
一般には、ダイクストラを使えばOKですが、Python だとギリギリ TLE になります。
そこで、ダイクストラより効率的な 01-BFS を利用します。（これは、リンクの重みが 0 / 1 だけの場合に使えます。）
※ 01-BFS の解説はこちらがお勧め。
betrue12.hateblo.jp
で、実際の結果はこうなります。
いちおうパスしていますが、1838 ms で、けっこうギリギリ感はあります。
重み 0 でつながるノードを同一視
上記のコードでは、conv() 関数で、「座標 + 方向（0 / 1 で表現）」で表した状態を単一の数値のノード番号に変換しています。
仮に、(1, 1, 0) と (2, 1, 0) が重み 0 のリンクで繋がっていた場合、これらを区別せずに同一のノード番号にマッピングしてしまっても構いません。
ただし・・・・
それぞれのノードがリンクを持っている場合、それぞれのリンクを融合するという、ちょっと面倒な処理が必要になります。
なのですが・・・
上記のコードでは、リンク情報を構築する際に、
for y in range(1, H+1): for x in range(1, W+1):
という方向にマス目をスキャンしながら、
・(x, y) から見て、右と下にあるマス目 (x+1, y)、および、(x, y+1) とのリンクを追加する
という処理をしています。（この順番であれば、左と上のマス目は、ダブルカウントになるので、考えなくてよいですよね・・）
そうすると・・・
・(x, y) から見て、右と下にあるマス目 (x+1, y)、および、(x, y+1) は、スキャン前なので、まだリンク情報を持っていません。
したがって、「(x+1, y)、もしくは、(x, y+1) を (x, y) と同一視する」という処理、つまり、「(x+1, y)、もしくは、(x, y+1) を (x, y) と同一のノード番号にマッピングする」という処理は、リンクの引き継ぎを気にせずに行うことができます。
ノードの同一視については、（Union-Find の発想を借りて）次のように実装します。
まず、conv() では、ノード番号を取得した後、さらにその親のノード番号を返すようにします。
def conv(x, y, d): global H, W, parent i = x + (y-1) * W + d * (H*W) if parent[i] == None: parent[i] = i return parent[i]
で、ノードを同一視させたくなったところで、親の情報を書き換えます。
if exists(x+1, y): p0 = conv(x, y, 0) p1 = conv(x+1, y, 0) parent[p1] = p0
一般には、親の親を再帰的に検索する必要がありますが、今回の場合は、スキャンの順序を（落ち着いて）考えると、再帰的な検索は不要とわかります。
実際にこれを実装したのがこちらになります。
801 ms で、確かに高速化されました。（ちなみに、この処理をしておけば、ダイクストラでもギリギリ間に合いました。）
とことんやってみる
上記のコードでは、隣り合うマス目を（連鎖的に）同一視していますが、よく考えると、スタート地点とゴール地点の方向転換についても、同一視ができます。（スタートとゴールでは方向転換のリンクは重み 0 なので。）
ただし、この部分では、先に触れたノードの引き継ぎが必要になります。さらに、同一視の連鎖が一方向にならない可能性があるので、（本物の Union-Find と同様に）親の検索を再帰的に実装する必要があります。
def conv(x, y, d): global H, W, parent i = x + (y-1) * W + d * (H*W) if parent[i] == None: parent[i] = i while i != parent[i]: i = parent[i] return i
ここまでやる必要があるかは疑問ですが、仮に、ここまでやると、重み 0 のリンクが完全になくなり、重み 1 のリンクのみになります。なので、01-BFS ではなく、普通の BFS での探索が可能になります。
というわけで、ものは試しでやってみました。
965 ms とちょっと遅くなりました。親の再帰的な検索の時間がオーバーヘッドになっているような気がします。（たぶん。）
