提示: 欢迎访问OurACM平台。
Problem 2028 时空门问题

Accept: 208    Submit: 1377
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在一个N*M的地图上旅行。地图上有些地方可以走用. 表示,不能走用 # 表示。在可以走的地方上下左右移动一格需要一个单位时间。可以走的地方还有一些时空之门。时空之门可以减少旅行的时间。如果 A 到 B 有一道时空之门,那么从 A 到 B 经过时空之门只要 1 个单位时间。在一个点可以有很多门通向其他的不同点。现在 john 在 s 点,他想以最快的时间到 t 点。求出最短时间。

Input

输入包含多组数据 输入数据第一行两个正整数 N M (1< n,m <= 500) 接着 N 行,每行 M 个字符 表示地图。#表示不可走,.表示可以走,s表示开始位置,t表示终止位置。一个地图中只有一个s与1个t. 接着 N*M 行,给出每个点的时空之门。按行优先给出,即给出的顺序为(1,1),(1,2) ….. (1,m) ,(2,1)....(2,m)....。 每行第一个数 K 表示该点的时空之门数,接着给出 K 个点,表示该点通向这k个点的时间为1。其中时空之门的个数不超过100000。对于50%的数据,时空之门的个数为0 在给出的数据中,不能走的点#的时空之门数一定为0,且没有通向不能走的点的时空之门。

Output

s 到 t 的最短时间。数据保证s可以走到t。

Sample Input

2 2 s# t. 0 0 0 0

Sample Output

1

Source

福州大学第八届程序设计竞赛

Submit  Back  Status  Discuss