【（高卒）国家一般職・平成２５年度・Ｎｏ．１８】（経路問題の元祖）格子状道路を通る最短経路問題【行政・高卒区分】

YouTube講義はこちら

【（高卒）国家一般職・平成２５年度・Ｎｏ．１８】（経路問題の元祖）格子状道路を通る最短経路問題【行政・高卒区分】

平成２５年度・国家一般職（高卒区分）No.18の問題です。
経路問題の元祖ともいうべき問題であり、『格子状道路』を通る最短経路の組合せの数が問われています。

経路問題の基礎を固める上で非常に重要な問題ですので、しっかりと理解するようにしてください。

経路を分割して考える（Ａ→Ｂ）

問題で問われているのは『Ａ→Ｂ→Ｃ→Ｄ→Ａ』と戻ってくる最短経路の組合せですが、まず最初に『Ａ→Ｂ』の組合せを考えてみます。

格子状道路の問題における必須テクニックですが、まず最初にＡと直線でつながっている格子点に１を書き、その後は『左と下の数字を足した数』を左下から右上へと順次記入していくことで、最短経路のパターン数を数えることができます。

Ｂ→Ｃの間の最短経路数

『Ｂ』から『Ｃ』までの最短経路数については、ＢとＣの位置関係がＡとＢの位置関係と全く同じであることから、１０通りであることが分かります。

Ｃ→Ｄの間の最短経路数

ＡＢ間と同様の方法で最短経路数を数えてみると４通りであることが分かります。