题目描述(ID:12279)
标题: 追赶
标签: 搜索 深度优先搜索 广度优先搜索
详情:
D先生天生爱赌。现在他已经欠下一屁股的债,被仇家追杀。D先生逃到一个迷宫中,仇家也追到了这儿。迷宫由编号由1到n的方块组成。每两个不同的方块将被得知它们是否与另一个相邻。现在已知D先生和仇家所处迷宫的位置。在迷宫中的人可以选择留在原地不动,还是移到相邻的方格中。
迷宫具有如下性质:
它不包括三角形,也就是没有任意三个不同的方块,它们两两相邻,
每一个玩家到达都能到达任意一个方块。
一次追杀由许多回合组成。在一个回合内,每一个人移一步。每一个回合由D先生开始。如果D先生与仇家在同一个方格中相遇,那么我们就可能永远见不到他了。
D先生非常害怕,他请求你告诉他是否会被仇家抓住, 多少回合仇家赶上他。(假设两个人都足够聪明)
输入格式:
文件的第一行有4个整数n, m, a 和b,它们用单个空格分隔。2<=n<=3000, n-1<=m<=15000, 1<=a,b<=n ,a 
输出格式:
一个单词NO ,如果玩家 B不能赶上玩家A, 或者 
  一个整数-如果玩家B能赶上玩家A的最少游戏轮数
样例:

输入

9 11 9 4
1 2
3 2
1 4
4 7
7 5
5 1
6 9
8 5
9 8
5 3
4 8

输出

3
登录并解答