A4762.关系网络

入门

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

nn 个人,每个人的编号为 1,2,,n1,n1,2,\dots,n-1,n

有一些人相互认识,如果现在 xx 想要认识 yy,那么他可以通过他所认识的人来认识更多的人。

例: 如果 aa 认识 bbbb 认识 cc,那么 aa 可以通过 bb 来认识 cc

现在需要你求出 xx 最少需要通过多少人才能认识 yy

数据范围

1n1001 \leq n \leq 100
0ai,j10 \leq a_{i,j} \leq 1

输入格式

第一行输入三个整数n,x,yn,x,y

随后输入nn行,每行输入nn个整数,代表存在着一个大小为N×NN \times N的邻接矩阵 aa ,且任意两数之间带有空格。

ai,j=1a_{i,j} = 1,则代表ii认识jj

ai,j=0a_{i,j} = 0,则代表ii不认识jj

输出格式

输出一行一个数,表示 xx 认识 yy 最少需要通过的人数。

输入输出样例

  • 输入#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
首页