Question

ー

この回答に載ってるまとめ方で求めたいのですが考え方が分かりません。どなたか教えてください。

図のように,東西に走る道が4本,南北に走る道が4本
の
い ルる見 目安15分
例題 36 最短経路の数
図のように,東西に走る道が4本,南北に走る道が4本 ×,
ある。A地点からB地点に行く経路のうち最短の経路4
は「アイ]通りあり, A地点から C地点と D地点の両方
を通ってB地点に行く経路のうち最短の経路は「ウ
北
B
CI
西
東
15分
通りある。
1039
並A
南
O

え
第
ある地点Pにたどり着く直前の点が Q, Rの2つ
あり,スタートから Q. Rまでの経路の数がそれぞ
れa, b通りであるとする。このとき, スタートか
らPまでの経路の数は
(Qを経由する経路の数)+(R を経由する経路の数)
すなわち(a+b)通りである。
この考え方を,スタート地点から各点について適用
していくと,経路の数が求められる。
この解法は,通れない点があるなど, 経路が複雑な
場合に特に有効である。
NorE
15
Q
P
a通り
A (a+b)通り
R
b通り
下エ
京 (8)
各点に経路の数を書き込
んでいく。
(別解)(ウ)
|3
6
右の図から
ウ6 通り
B
*直前の点に書かれた数字
3
3
3
を足していく。
D
1
|2
1
A
C

Answer 1

T

AからCまでをまず考えると、
↑↑→の並び替えより3通り
DからBまでを考えると
↑→の並び替えより2通り
3×2=6より
6通り