← 返回题目列表

AtCoder · icpc2014spring_i

I. 东京奥林匹克中心

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

问题陈述

您正在参加编程竞赛夏令营。 训练营在一个名为 东京奥林匹克中心。 今天是夏令营的最后一天。 不幸的是,您被命令检查所有参与者是否已正确清洁他们的房间。

住宿设施是一个矩形场地,其高度为$H$,宽度为$W$。 该字段被划分为方形单元。 行从上到下编号为 $1$ 到 $H$ 列从左到右编号为 $1$ 到 $W$。 $i$ 行、$j$ 列中的单元格用 $(i, j)$ 表示。 如果两个单元共享一条边,则它们是相邻的。

每个单元被称为 壁细胞 或 地板单元。 壁细胞代表一堵无人能进入的墙。 楼层单元是住宿设施内部的一部分。 每个人都可以在两个相邻的楼层单元之间移动。 楼层单元被分成几个单元。 每个单元都分配有一个大写英文字母(A, B, C,...)。 与一个楼层单元恰好相邻的楼层单元称为 房间。 否则,地板单元称为 过道。 例如,住宿设施可以如下图所示。 我们将壁细胞表示为 . (单期)。

...................
.....AAABBBBBBB....
...A.AA.A...B.B..B.
..AAAAAAAABBBBBBBB.
...A..A.A.....B....
......A.......BBBB.
....A.AA..C.C...B..
...AAAAACCCCCCBBBB.
...A..A...C.C...B..
...................

上图中,A 单元有 $7$ 房间,B 单元有 $4$ 房间,C 单元有 $4$ 房间。

由于住宿设施太大,无法单独探索,所以你让营地的其他参与者检查房间。 为了简单起见,我们称它们为 工作人员。 现在,$(s, t)$ 牢房有 $K$ 名工作人员。 您决定按照以下程序检查房间。

  1. 首先,您将每个员工分配到一些单位。 每个单位必须分配给一名工作人员。 请注意,可以将所有单元分配给一名人员,也可以不将单元分配给某些人员。

  2. 然后,各个工作人员同时开始检查指定单元的房间。 工作人员可以在 $T_{\mathit{move}}$ 时间内在两个相邻的楼层单元之间移动。 要检查 $(i, j)$ 的房间,工作人员必须移动到 $(i, j)$ 单元并在那里花费 $T_{\mathit{check}}$ 时间。 每位工作人员首先确定要检查的单元的顺序,并且必须按照顺序检查房间。 例如,假设有一名员工被分配到单位 A、C 和 E。 他可能决定顺序是E->A->C。 之后,他必须先检查E单元的所有房间。 然后,他必须检查A单元的所有房间,依此类推。 工作人员可以通过任何楼层牢房。 但工作人员无法检查未分配给他们的房间。 此外,工作人员不能按照他们决定的单位顺序检查房间。

  3. 检查完所有分配的房间后,工作人员必须返回牢房$(s,t)$。

  4. 当所有人员返回单元格$(s,t)$时,任务完成。

因为您在下一次比赛之前没有足够的时间,所以您希望尽量减少检查所有房间的总时间。


输入

输入的第一行包含三个整数 $H$、$W$ 和 $K$($1 \le H \le 50$、$1 \le W \le 50$、$1 \le K \le 12$)。 第二行包含四个整数$s$、$t$、$T_{\mathit{move}}$和$T_{\mathit{check}}$($1 \le s \le H$、$1 \le t \le W$、$1 \le T_{\mathit{move}}、T_{\mathit{check}} \le 10{,}000$)。 以下每一行 $H$ 均包含 $W$ 字符。 每个字符代表住宿设施中的一个单元格。 这些行中第 $i$ 行中的第 $j$ 个字符是 . 如果单元格 $(i, j)$ 是壁单元格。 否则,该字符是大写英文字母(A-L) 表示单元格 $(i, j)$ 所属的单元。

您可以假设满足以下条件。

  • 每个单元的房间数量在 1 美元到 12 美元之间(含)。

  • 单元格 $(s, t)$ 保证是一个过道。

  • 每个单元的楼层单元都是相连的。

  • 现场的楼层单元已连接。

  • 每个单元至少包含两个单元。

输出

输出检查一行中所有房间所需的最短时间。


示例输入 1

3 3 1
1 1 10 10
AAA
A..
A..

样本输入 1 的输出

100

示例输入 2

3 3 2
1 1 10 10
ABB
A..
A..

样本输入 2 的输出

50

示例输入 3

5 10 3
3 6 1 100
...G.H.A..
.AAGAHAABB
FFAAAAAAA.
.EEAAADACC
..E...D...

样本输入 3 的输出

316

示例输入 4

10 19 2
6 15 3 10
...................
.....AAABBBBBBB....
...A.AA.A...B.B..B.
..AAAAAAAABBBBBBBB.
...A..A.A.....B....
......A.......BBBB.
....A.AA..C.C...B..
...AAAAACCCCCCBBBB.
...A..A...C.C...B..
...................

样本输入 4 的输出

232

示例输入 5

27 36 6
24 19 616 1933
....................................
..........B...............B.........
..........BBB..........BBBB.........
..........BBBBB.......BBBB..........
...........BBBBBBBBBBBBBBB..........
...........BBBBBBBBBBBBBBB..........
...........BBBBBBBBBBBBBB...........
............BBBBBBBBBBBBB...........
...........BBBBBBBBBBBBBBB..........
..........BBBBBBBBBBBBBBBBB.........
......B...BBBBBBBBBBBBBBBBB...B.....
......BB.BBBBBBBBBBBBBBBBBB..BB.....
.......BBBBBBBBBBBBBBBBBBBB.BB......
.........BBBBBBBBBBBBBBBBBBBB.......
........BBBBB..BBBBBBBB..BBBBB......
......BBBBBB....BBBBB....BBBBBB.....
.....BBBBBBBB...BBBBB..BBBBBBBB.B...
...BBBBBBB..B...BBBBB..B..BBBBBBBB..
.BBBBBBBBB.....BBBBBBB......BBBBBBB.
..BBBBBBB......BBBBBBB........BBB...
.BBBB.........BBBBBBBBB........BBB..
..............BBBBBBBBB.............
.............BBBBBBBBBB.............
.............BBBBBBBBBB.............
..............BBBBBBBB..............
..............BBBBBBBB..............
....................................

样本输入 5 的输出

137071