Решить задачу надо не посчитав количество, а по формуле. Теорема графов, если не ошибаюсь. Объясните пожалуйста, Как найти.
Answers & Comments
Segrif
Не думаю, что есть какие-то формулы. В любом случае придется считать.
Идея решения большинства таких задача следующая: Как можно попасть в город H? Можно прийти в него из городов D, F, G или E. Соответственно, количество путей из A в H - это количество путей из A в D + из A в F + из A в G + из A в E. Аналогично для остальных городов. Будем считать, что существует один путь из A в A. В город B можно попасть только напрямую из A - 1 путь. В C тоже можно попасть только напрямую из A - 1 путь. В E можно попасть только из C. В C существует 1 путь -> в E тоже 1 путь. В F можно попасть из A,B,C,E -> количество путей в F = 1 + 1 + 1 + 1 = 4 В D можно попасть из B или F - 1 + 4 = 5 В G можно попасть только из E - 1 Наконец, количество путей в H = 5 + 4 + 1 + 1 = 11
Answers & Comments
Идея решения большинства таких задача следующая:
Как можно попасть в город H? Можно прийти в него из городов D, F, G или E.
Соответственно, количество путей из A в H - это количество путей из A в D + из A в F + из A в G + из A в E.
Аналогично для остальных городов.
Будем считать, что существует один путь из A в A.
В город B можно попасть только напрямую из A - 1 путь.
В C тоже можно попасть только напрямую из A - 1 путь.
В E можно попасть только из C. В C существует 1 путь -> в E тоже 1 путь.
В F можно попасть из A,B,C,E -> количество путей в F = 1 + 1 + 1 + 1 = 4
В D можно попасть из B или F - 1 + 4 = 5
В G можно попасть только из E - 1
Наконец, количество путей в H = 5 + 4 + 1 + 1 = 11
Ответ: 11