#P1258. 2023.04.27-春招-第四题-路径数量
2023.04.27-春招-第四题-路径数量
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥是一个喜欢探险的小男孩,他有一天发现了一张神秘的地图,上面标注了一些奇怪的符号和箭头。
他觉得这是一张藏宝图,并且这个藏宝图是一个有向图,于是他决定去寻找宝藏。地图上的符号代表了不同的地点,箭头代表了可以从一个地点到达另一个地点的路线。
地图上有两个特殊的符号,S和E,分别代表了起点和终点。(这张图只有S无入度,只有E无出度)塔子哥想要从起点出发,到达终点,同时经过某个指定的地点,比如一个古老的神庙或一个美丽的瀑布。
他想知道有多少种不同的路线可以满足他的要求,他的要求如下:
你能帮他计算出有多少种路线吗?
第一行为一个字符串 str
,表示指定节点。
接下来若干行,每一行为两个字符串 s1
和 s2
,表示节点 s1
到节点 s2
有一条边。
1≤节点个数≤10
保证输入的是一个合法的有向图。不含自环,不含重边.指定节点不是S,E
输出为一个整数,表示从S节点开始E节点结束且经过指定节点 str
的路径数量。
输入
2
S 1
S 1a
1 2
1a 2
2 3
3 E
输出
2
样例解释
样例一输入的图如下:
由上可知以S作为起点,E作为终点并且经过节点2的路径有两条。
输入
3
S 1
1 2
2 1
2 3
3 E
输出
2
样例解释
样例二输入的图如下:
由上可知以S作为起点,E作为终点并且经过节点3的路径有一下两条路径:
S->1->2->3->E
和 S->1->2->1->2->3->E
。
其中第二条路径走了一次环,然后跳出了环,因为题目要求环不能走两次及以上。
输入
a3
a3 a5
a3 a4
a4 a5
a4 a3
a5 a3
S a5
a5 E
输出
5
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.