关系网络

时间限制：1秒        内存限制：128M

题目描述

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

输入描述

第一行3个整数n、x、y,2<=n<=100 

接下来n行是一个nxn的邻接矩阵，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

样例

输入

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

代码：

#include<iostream>
using namespace std;
int n,a[105][105],q[105],dep[105],f,r,x,y,vis[105];
void bfs(int i){
    q[r++]=i;
    vis[i]=1;
    dep[i]=1;
    while(f<r){
        int point=q[f];
        for(int j=1;j<=n;j++){
            if(a[point][j]==1&&vis[j]==0){
                q[r++]=j;
                vis[j]=1;
                dep[j]=dep[point]+1;
            }
        }
        f++;
    }
}
int main(){
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    bfs(x);
    cout<<dep[y]-2;
    return 0;
}