A4450. 【搜索】【广度优先】关系网络
编程题
普及-
知识点
题目描述
有 $n$ 个人，编号为 $1\sim n$。其中有一些人相互认识，现在 $x$ 想要认识 $y$，可以通过他所认识的人来认识更多的人（如果 $a$ 认识 $b$、$b$ 认识 $c$，那么 $a$ 可以通过 $b$ 来认识 $c$），求出 $x$ 最少需要通过多少人才能认识 $y$。
输入格式
第 $1$ 行 $3$ 个正整数 $n,x,y$，其中：$n\le 100,1\le x,y\le n$。
接下来是一个 $n\times n$ 的邻接矩阵，
保证 $i=j$ 时，$a[i][j]=0$，并且 $a[i][j]=a[j][i]$，一行中的两个数之间有一个空格。
接下来是一个 $n\times n$ 的邻接矩阵，
a[i][j]=1 表示 $i$ 认识 $j$，a[i][j]=0 表示 $i$ 不认识 $j$。 保证 $i=j$ 时，$a[i][j]=0$，并且 $a[i][j]=a[j][i]$，一行中的两个数之间有一个空格。
输出格式
输出一行一个数，表示 $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
输出 #1
2