Race

题意翻译

## 题目描述 老城是一个矩形城市，表示为m×n块网格。这座城市包含许多建筑物、笔直的双向街道和路口。每个路口和每个建筑物都恰好是一个街区。所有的街道都有一个街区的宽度，可以是垂直的，也可以是水平的。每条街的两边都有一个路口。当且仅当它们共享一个公共边时，我们才称两个块相邻。没有两个不同街道的街区是相邻的，也没有两个路口是相邻的。 每年都有一个节日，作为节日的一部分，Peykan 沿着城市的一条特殊路径走。这条路径从街道的一个街区开始，经过许多交叉路口，并在某个街道的一个街区结束。对于每个街区，我们知道 Peykan 从这个街区到相邻街区需要多长时间。此外，Peykan 可以在一分钟内从每个路口到达其相邻的街区。 我们知道 Peykan 的初始位置以及它到达目的地所经过的路口序列。经过所有的路口，到达目的地后，它会永远停留在那里。你的任务是找出 Peykan 开始移动 k 分钟后会在哪里。 考虑到 Peykan 总是遵循通过给定交叉路口序列并到达目的地的最短路径。 请注意，Peykan 可能会多次访问某些街区。 ## 输入格式 输入的第一行包含三个整数 m , n 和 k (3<=m,n<=100,1<=k<=100000). 接下来m行代表城市的地图。每行有n个字符，每个字符是一个街区： - 字符“#”代表建筑物。 - 数字“1”,“2”,......，“9”代表一个街区，这个数字表示 Peykan 通过这个街区所需的时间(单位:分钟)。 - 字符“a”,“b”,....., "z" 表示这个街区是一个路口，这个字符是它的名字。所有路口名称都是唯一的。 考虑所有街区都有坐标：第i行第j个有坐标(i,j) (1<=i<=m,1<=j<=n). 第 $ (m+2) $ 行 包含2个整数 $ r_{s} $ 和 $ c_{s} $ $ (1<=r_{s}<=m,1<=c_{s}<=n) $ , 字符串 $ s $ 和另外2个整数 $ r_{e} $ 和 $ c_{e} $ $ (1<=r_{e}<=m,1<=c_{e}<=n) $ . 路线从街区 $ (r_{s},c_{s}) $ 开始 , 按照指定的顺序继续通过路口 $ s $ ,在街区 w$ (r_{e},c_{e}) $ 结束 . $ s $ 的长度在 $ 1 $ 到 $ 1000 $ 之间 . 保证字符串 $ s $ 表示从开始位置到结束位置的正确路径并且字符串 $ s $ 不包含两个连续相等的字母. 起始位置$（r_{s}，c_{s}）$和结束位置$（r_{e}，c_{e}）$也是街区. ## 输出格式 一行,输出2个整数$ r_{f} $ 和 $ c_{f} $ — ( $ r_{f},c_{f} $ )正好是 Peykan 第k分钟的位置。 ## 样例 #1 ### 样例输入 #1 ``` 3 10 12 ########## #z1a1111b# ########## 2 3 ab 2 8 ``` ### 样例输出 #1 ``` 2 8 ``` ## 样例 #2 ### 样例输入 #2 ``` 10 3 5 ### #w# #1# #a# #1# #1# #1# #1# #b# ### 3 2 abababababababab 6 2 ``` ### 样例输出 #2 ``` 8 2 ``` ## 样例 #3 ### 样例输入 #3 ``` 3 10 6 ########## #z1a1311b# ########## 2 3 ab 2 8 ``` ### 样例输出 #3 ``` 2 7 ```

题目描述

The Old City is a rectangular city represented as an $ m×n $ grid of blocks. This city contains many buildings, straight two-way streets and junctions. Each junction and each building is exactly one block. All the streets have width of one block and are either vertical or horizontal. There is a junction on both sides of each street. We call two blocks adjacent if and only if they share a common side. No two blocks of different streets are adjacent and no two junctions are adjacent. There is an annual festival and as a part of it, The Old Peykan follows a special path in the city. This path starts from a block in a street, continues with many junctions and ends in a block of some street. For each street block, we know how much time it takes for the Old Peykan to go from this block to an adjacent block. Also the Old Peykan can go from each junction to its adjacent street blocks in one minute. Of course Old Peykan can't go to building blocks. We know the initial position of the Old Peykan and the sequence of junctions that it passes to reach its destination. After passing all the junctions and reaching the destination, it will stay there forever. Your task is to find out where will the Old Peykan be $ k $ minutes after it starts moving. Consider that The Old Peykan always follows the shortest path that passes through the given sequence of junctions and reaches the destination. Note that the Old Peykan may visit some blocks more than once.

输入输出格式

输入格式

The first line of input contains three integers $ m $ , $ n $ and $ k $ $ (3<=m,n<=100,1<=k<=100000) $ . Next $ m $ lines are representing the city's map. Each of them containts $ n $ characters, each character is a block: - Character "\#" represents a building. - Digits "1", "2", $ ... $ , "9" represent a block of an street and this digit means the number of minutes it takes for the Old Peykan to pass this block. - Characters "a", "b", $ ... $ , "z" means that this block is a junction and this character is it's name. All the junction names are unique. Consider that all blocks have the coordinates: the $ j $ -th in the $ i $ -th line have coordinates $ (i,j) $ $ (1<=i<=m,1<=j<=n) $ . The $ (m+2) $ th line contains two integers $ r_{s} $ and $ c_{s} $ $ (1<=r_{s}<=m,1<=c_{s}<=n) $ , string $ s $ and another two integers $ r_{e} $ and $ c_{e} $ $ (1<=r_{e}<=m,1<=c_{e}<=n) $ . The path starts from block $ (r_{s},c_{s}) $ , continues through junctions in the order that is specified by $ s $ and will end in block $ (r_{e},c_{e}) $ . Length of $ s $ is between $ 1 $ and $ 1000 $ . It's guaranteed that string $ s $ denotes a correct path from the start position to the end position and string $ s $ doesn't contain two consecutive equal letters. Also start position $ (r_{s},c_{s}) $ and the end position $ (r_{e},c_{e}) $ are street blocks.

输出格式

In a single line print two integers $ r_{f} $ and $ c_{f} $ — ( $ r_{f},c_{f} $ ) being the position of the Old Peykan after exactly $ k $ minutes.

输入输出样例

输入样例 #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