この問題の解き方を教えていただきたいです

締切済

質問者：ハニーー
質問日時：2019/01/24 22:57
回答数：1件

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (1件)

最新から表示
回答順に表示

No.1

回答者：ありものがたり
回答日時：2019/01/25 03:45

添付の図のようにC地点、D地点を置きましょう。

縦mステップ、横nステップの長方形の対角線を結ぶ最短路が(m+n)Cmとおりなので、

(Cを通るAからBへの最短路数)=(AからCへの最短路数)×(CからBへの最短路数)
=(6C3)(5C2)=200.

(Dを通るAからBへの最短路数)=(AからDへの最短路数)×(DからBへの最短路数)
=(8C3)(3C2)=168.

(CもDも通るAからBへの最短路数)=(AからCへの最短路数)×(CからDへの最短路数)×(DからBへの最短路数)
=(6C3)(2C0)(3C2)=60.

(Cは通りDは通らないAからBへの最短路数)=(Cを通るAからBへの最短路数)-(CもDも通るAからBへの最短路数)
=200-60=140.

(Dは通りCは通らないAからBへの最短路数)=(Dを通るAからBへの最短路数)-(CもDも通るAからBへの最短路数)
=168-60=108.

(AからBへの最短路数)=(CもDも通るAからBへの最短路数)＋(Cは通りDは通らないAからBへの最短路数)＋(Dは通りCは通らないAからBへの最短路数)
=60+140+108=308.