1699 - pyy's road
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 35
Solved: 9
- Description
有一天,路痴pyy来到了主校区。然后迷路了。。。
他知道主校区的路都是横平竖直的,所以他只能往上下左右四个方向走。
他还有一张奇怪的地图(要是不奇怪就不会迷路了)。
地图有N行M列,每一个位置是 @ 或者 # 。
@表示这里可以通过,#表示这里不能通过。
这张地图标记出当前的位置,和终点的位置。
pyy现在想知道从当前位置到终点 最短 还有多远。
如果pyy不能走到终点,会大骂一句“垃圾道路”。
注意:众所周知,学校周围是有栏杆的。作为好学生的pyy不会翻越这些栏杆,去抄近路。
换而言之,pyy不会走出地图。
- Input
第一行为数据组数T
每组数据的第一行为N, M。代表地图有N行M列。
第二行为Xs,Yx,Xt,Yt。表示当前的坐标和终点的坐标(从1开始)。
接下来的N行,每行M个字符。输入保证这些字符只可能为@或者#。
1 <= T <= 10
1 <= N, M <= 1000, 1 <= Xs, Xt <= N, 1 <= Yx, Yt <= M。
- Output
对于每组数据输出一行。
如果可以走到,输出"Case #ti: d"(去掉引号)。ti为第几组数据,d为最短的距离。
如果不能走到,输出"Case #ti: lj road"(去掉引号)。ti同上。
- sample input
-
2 2 2 1 1 2 2 @@ @@ 2 2 1 1 2 2 @# #@
- sample output
-
Case #1: 2 Case #2: lj road
- hint
- source
- pyy