2017年华中科技大学ACM招新赛

From: 2016-12-18 12:30:00 To: 2016-12-18 17:30:00 Now: 2017-09-24 21:46:19 Status: Public

H - pyy's road

Time Limit: 1s Memory Limit: 128MB

Submissions: 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