TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4313
  • 题目
  • P4313营救
    限制 : 时间限制 : - MS   空间限制 : 565536 KB
    评测说明 : 2s
    问题描述

    一个乡村发了洪水,有多名村民被困,村子是 n × m 的网格,网格中. 号代表平地, # 号代表该地已被洪水淹没, A 、B ……等大写字母表示该地有村民被困。现在只有你去营救村民,网格中 s 代表营救的起点, t 代表营救的终点。

    你的初始速度为 k 秒一格,每次可以向上下左右 4 个方向中的一个移动 1 格。在背上一个村民后,速度可能会降低,也可能会加快,但速度不能快于 1 秒每格。问,最快需要多长时间将所有村民救出?

    注意:不能在终点以外的地方放下村民;可以同时背多个村民。

    输入格式

    第一行 3 个正整数 n, m, k,分别表示村庄长度、宽度、你的初始速度。

    接下来 n 行,每行一个长度为 m 的字符串,表示村庄的地形,字符串意义如上所述。

    接下来若干行,每行一个大写字母、一个整数,表示该编号的村民会使 k 增加 / 减少多少。行数等同于地形中大写字母的个数。大写字母按字典序,即A 、B 、C 的顺序排列,保证前后两行的字母是连续的。

    输出格式

    输出 1 个整数,表示最小用时。

    样例输入 1

    4 4 2
    s.##
    ..A#
    .B##
    ...t
    A -3
    B 4

    样例输出 1

    17

    样例输入 2

    4 4 3
    AsB.
    ###.
    #...
    ##t#
    A 4
    B -6

    样例输出 2

    12

    提示

    对于 10% 的数据,满足 1 ≤ n, m ≤ 5,村民个数为 1;
    对于 50% 的数据,满足 1 ≤ n, m ≤ 5,村民个数小于等于 5;
    对于 100% 的数据,满足 1 ≤ n, m ≤ 10,村民个数小于等于 10。


    来源  计蒜客