入门OJ 1278【关系网络】

描述

有N个人，编号为1到N，其中有一些人互相认识，现在x想认识y,可以通过他所认识的人来认识更多的人
如果x认识y,y认识z,则x可以通过y来认识z,求出x最少需要通过多少人才能认识y

输入输出格式

输入

第一行3个整数n,x,y,N<=100,1<=x,y<=N
接下来是一个N*N的矩阵，a[i,j]=1则说明i认识j,如果为0则不认识
保证i=j时，a[i,j]=0,且a[i,j]=a[j,i]
行中每两个数字之间用一个空格分开

输出

如题

输入输出样例

输入样例1

输出样例1

解题思路

　　典型的BFS，直接搜就行了，最后输出时记得减一，因为要到达的人自己不算。

题解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,x,y;
 4 struct node{
 5     int num;//编号 
 6     int t;//步数 
 7     node(){}
 8     node(int sum,int tt)
 9     {
10         num=sum;
11         t=tt;
12     }
13 };
14 int mp[101][101];//图 
15 bool flag[101];//标记 
16 queue<node> q;
17 void bfs()
18 {
19     q.push(node(x,0));
20     flag[x]=true;//打标记 
21     while(!q.empty())
22     {
23         node head=q.front();
24         q.pop();
25         if(head.num==y)
26         {
27             cout<<head.t-1;//一定要减一 
28             return;
29         }
30         for(int i=1;i<=n;i++)
31         {
32             if(mp[head.num][i]&&!flag[i])
33             {
34                 flag[i]=true;
35                 q.push(node(i,head.t+1));
36             }
37         }
38     }
39 }
40 int main()
41 {
42     cin>>n>>x>>y;
43     for(int i=1;i<=n;i++)
44     {
45         for(int j=1;j<=n;j++)
46         {
47             cin>>mp[i][j];//存图 
48         }
49     }
50     bfs();
51 }