Задача №112640. Сколько путей
Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, сколько всего есть разных маршрутов между городами A и B (маршруты не должны содержать циклов). Напишите программу, которая поможет Васе.
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 20 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему авиационных сообщений. В следующей строке вводятся номера начальной и конечной точек маршрута (городов); нумерация начинается с единицы.
В первой строке программа должна вывести количество найденных подходящих маршрутов M . В следующих M строках выводятся сами маршруты в виде последовательности номеров городов, которые нужно посетить. Маршруты должны быть упорядочены: сначала маршруты, у которых второй номер города имеет минимально возможный номер, из них сначала все маршруты, в которых третий номер города имеет минимально возможный номер, и т.д.
5 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 5
6 1 2 3 5 1 2 5 1 3 2 5 1 3 5 1 4 3 2 5 1 4 3 5