← 返回题目列表

Codeforces · 241/F

F. 比赛

中文机器翻译题面 查看原题

老城是一个矩形城市,由 m × n 的街区网格表示。这座城市有许多建筑物、笔直的双向街道和交叉路口。每个路口和每个建筑物都是一个街区。所有街道的宽度均为一个街区,要么是垂直的,要么是水平的。每条街道的两侧都有一个路口。当且仅当两个块共享公共边时,我们才称它们为相邻块。不同街道的两个街区不相邻,也不存在两个路口相邻。

每年都会举办一次节日,作为节日的一部分,老佩坎 (The Old Peykan) 遵循城市中的一条特殊道路。这条路径从一条街道的一个街区开始,经过许多路口,最终到达某个街道的一个街区。对于每个街区,我们知道老佩坎从这个街区到相邻街区需要多少时间。此外,Old Peykan 可以在一分钟内从每个路口到达邻近的街区。老佩坎当然不能去搭积木。

我们知道老佩坎的初始位置以及它到达目的地所经过的路口顺序。经过所有路口并到达目的地后,它将永远停留在那里。你的任务是找出老佩坎开始移动后 k 分钟的位置。考虑老佩坎始终遵循穿过给定顺序的路口并到达目的地的最短路径。

请注意,老佩坎可能会多次访问某些街区。

输入

输入的第一行包含三个整数 m、n 和 k (3 ≤ m, n ≤ 100, 1 ≤ k ≤ 100000)。接下来的 m 行代表城市的地图。每个包含n个字符,每个字符是一个块:

- 字符“#”代表建筑物。
- 数字“1”、“2”、...、“9”代表街道的一个街区,这个数字表示老佩坎通过这个街区所需的分钟数。
- 字符“a”,“b”,...,“z”表示该块是一个路口,并且该字符是它的名称。所有连接点名称都是唯一的。

考虑所有块都具有坐标:第 i 行中的第 j 个块具有坐标 (i, j) (1 ≤ i ≤ m, 1 ≤ j ≤ n)。

第 (m + 2) 行包含两个整数 rs 和 cs (1 ≤ rs ≤ m, 1 ≤ cs ≤ n)、字符串 s 和另外两个整数 re 和 ce (1 ≤ re ≤ m, 1 ≤ ce ≤ n)。该路径从块 (rs, cs) 开始,按照 s 指定的顺序继续通过交汇点,并以块 (re, ce) 结束。 s 的长度在 1 到 1000 之间。

保证字符串 s 表示从起始位置到结束位置的正确路径,并且字符串 s 不包含两个连续的相等字母。起始位置(rs,cs)和结束位置(re,ce)也是街道街区。

输出

在一行中打印两个整数 rf 和 cf — (rf, cf) 是 Old Peykan 在恰好 k 分钟后的位置。

示例

输入 #1

3 10 12
##########
#z1a1111b#
##########
2 3 ab 2 8

输出 #1

2 8

输入 #2

10 3 5
###
#w#
#1#
#a#
#1#
#1#
#1#
#1#
#b#
###
3 2 abababababababab 6 2

输出 #2

8 2

输入 #3

3 10 6
##########
#z1a1311b#
##########
2 3 ab 2 8

输出 #3

2 7