P74157

关系网络

难度 4 级 小学 算法入门 BFS
讨论 统计 24通过 27提交 88.9%通过率 旧版界面
时间限制 1 秒 内存限制 256 MB

题目描述

有n个人,他们的编号为1~n,其中有一些人相互认识,现在x想要认识y,可以通过他所认识的人来认识更多的人(如果a认识b,b认识c,那么a可以通过b来认识c),求出x最少需要通过多少人才能认识y。

输入

第1行3个整数n、x、y,2≤n≤100;

接下来的n行是一个n*n的邻接矩阵,a[i][j]=1,表示i认识 j,a[i][j]=0表示不认识。保证i=j时,a[i][j]=0,并且a[i][j]=a[j][i]。

输出

一行一个整数,表示x认识y最少需要通过的人数。数据保证x一定能认识y。

样例

样例 1
输入
5 1 5
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
0 0 0 1 0
输出
2

来源

课课通

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交