ITパスポート 平成22年度 秋期 問72

図 1 の A1 地点から C2 地点へ行くとき，通過する地点が最も少なくてすむ最短経路は，図 2 のように数えることによって 3 通りあることが分かる。A1 地点から，C2 地点を経由して，D4 地点へ行く最短経路は何通りあるか。

〔図1〕碁盤の目の地点（字で書き起こしたもの）

上          D1 ── D2 ── D3 ── D4
             │      │      │      │
            C1 ── C2 ── C3 ── C4
             │      │      │      │
            B1 ── B2 ── B3 ── B4
             │      │      │      │
下          A1 ── A2 ── A3 ── A4
            左                    右

A1（左下）が出発点、C2 と D4 に印が付いている。
行は下から A・B・C・D、列は左から 1・2・3・4。移動は右か上のみ（最短経路のため）。

〔図2〕A1 から C2 までの数え方（字で書き起こしたもの）

A1 ──→ B1 (1) ──→ C1 (1) ──┐
 │        │                  ├─→ C2 (3)
 │        └──→ B2 (2) ───────┘
 └──→ A2 (1) ──→ B2 (2)

（  ）内数字は，A1 からその地点までの最短経路の数を表す。