場合の数の問題です。道路の行き方が何通りあるかという問題です。

質問

＜問題＞
図のような道があります。AからBまで行くのにC、D、E、Fは全く通れず、同じ場所も1回しか通れない。道は左右方向が左から右の一方通行、上下方向はどちらへも進んで良いとするとき、AからBまでの行き方は何通りあるか？
＊＊＊＊＊＊＊＊＊＊＊＊＊＊
という問題です。上下にどちらでも行けるという点がややこしいです。
とき方を教えてください。宜しくお願いします。

回答No.2

nag0720 · ベストアンサー

もし、通行止めがないとすると、AからBまでの行き方は、6*6*6*6*6　です。

Cだけが通行止めだと、
(4*4+2*2)*6*6*6

さらに、D,Eが 通行止めだと、
(4*4+2*2)*(1*1+2*2+3*3)*6

さらに、Fが 通行止めだと、
(4*4+2*2)*(1*1+2*2+3*3)*4

なぜそういう式になるかは考えてみてください。

回答No.1

Kaisert

AからBまでは最短ルートで行かなければならない

とかあります？

補足

最短ルートでいくという条件はありません。
　・同じ場所が1回しかとおれない（同じ道も1回だけしか通れない）
　・上下には行けるが、左右は左から右への一方通行
という条件だけです。
宜しくお願いします。