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

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

No.2 ベストアンサー 回答者： nag0720 回答日時： 2009/08/17 23:47

もし、通行止めがないとすると、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 回答日時： 2009/08/17 23:37

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

とかあります？

この回答への補足

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

補足日時：2009/08/18 16:54