往届 ACM 队训练题 (参考)

1038. Kryie

单点时限: 5.0 sec

内存限制: 256 MB

BonBon 在 ecnu 闲逛的时候被 NGB 恶魔捉走了,McFn 找到了 NGB 的巢穴–325 基地。325 基地机关重重,一不小心就会掉进陷阱被抓住 >_<. 现在 McFn 手上有一份基地构造的资料,可以知道基地中所有机关的位置。

基地是一个构造大小为 N x N 的迷宫,某些方格是机关,某些方格是安全空地。McFn 现在处在迷宫的入口 , 位置是在 (0,0) 的 , 也就是迷宫的左上角 .BonBon 被困在 (N-1,N-1) 的位置,也就是迷宫的右下角 .

由于对基地的安全设施很放心,所以 NGB 没有设置看守,但是在基地的每个角落都设置了一种特殊传感器 MST, 如果同一个物体在基地的行走的线路中转向次数太多的话,MST 就会报警 !(因为它知道你是在进行暴力回溯法搜索路径-_-)

由于不知道 MST 的具体数据,所以为了能够安全的救出 BonBon,McFn 必须尽量减少在基地迷宫的行走中转弯的次数。所以他想知道要到达 BonBon 的位置,最少需要转向的次数。

当然在入口处你可以随便选择一个方向作为初始的方向 , 不算入转向次数中 .

入口处和 BonBon 所在处的机关都被 McFn 和 BonBon 破坏了 , 所以可以忽略不计

输入格式

第一行有一个整数 T,表示有 T 组测试数据

每组测试数据

第一行有两个整数 N,M.

N(2<=N<=500),M 表示陷阱的个数 (0<=M<=1000000);

接下来有 M 行,每行有 2 个整数 xi,yi;

表示 xi,yi 这个地方有一个机关。

hint 同一个位置可能会有多个机关 !

输出格式

每组测试数据输出一行,每行一个整数,要从基地入口走到 BonBon 的位置的所需要的最少转向次数。如果不存在一条路径 , 则输出 “Kryie!”.

样例

Input
2
3 2
1 1
1 2
3 3
1 0
1 1
1 2
input detail:
.表示空格,#表示障碍
case 1:
...
.##
...
case 2:
...
###
...
Output
1
Kryie!
不限期开放

题目列表