「格子状ルートにおける最短経路問題」は、どこかで一度はやったことがあるのではないでしょうか。
入試においては、
「通れないor通るべき箇所がある」、
「直交しないルートが含まれている」、
といったように、色々と設定をひねって出題されることが多くなります。
それらに対応できるようにするために、まずは基礎をしっかり固めておきましょう。
【問題】
下図のような格子状の道において、AからBへ行く最短の道筋は何通りあるか。
但し、対角線ABは道ではなく、これに触れてもよいが、横切ってはいけないものとする。
(答え；46）
【解説】
この程度であれば、定番の
「順番に経路数を書き込んでいく方法」
で求めても構わないでしょう。
しかし、応用問題に対応できるようにしておくために、次のような考え方ができるようにしておきましょう。
まず、
「対角線下のA→Bの経路」
は、
「対角線上のB→Aの経路」
と同じなので、一方のみの検討で済みますね。
下半分で考えてみると、次の2パターンしかないことに気づけるようになりましょう。
(1) (6×5)/(2×1)-1=14
(2) (5×4)/(2×1)-1=9
∴(14+9)×2=46通り
