← 返回题目列表

Codeforces · 513/F2

F2. 斯凯格老板

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

克苏鲁决定抓住 Scaygerboss。 Scaygerboss 发现了这一点,并试图藏在他的一群 Scayger 中。除 Scaygerboss 外,所有 Scayger 要么是雄性,要么是雌性。 Scaygerboss 的性别是“其他”。

Scaygers 分散在分为单元格的二维地图上。如果一只斯凯奇与一只与其性别不同的斯凯奇呆在同一个牢房里,那么它就会显得书呆子又可爱。如果地图上所有的斯凯格虫看起来都像书呆子一样可爱,克苏鲁将无法抓住斯凯格老大。

镰刀虫可以以不同的速度移动。对于每个 Scayger,我们都会得到该 Scayger 从一个单元格移动到相邻单元格所需的时间。如果单元格共享公共边,则它们是相邻的。在任何时间点,每个不包含障碍物的单元格都可以被任意数量的 Scayger 占据。 Scaygers 无法移动到有障碍物的单元格中。

计算最短时间,让所有 Scayger 看起来既书呆子又可爱,前提是它们以最佳方式朝着这个目标前进。

输入

第一行包含 4 个整数:n、m、男性、女性(0 ≤ 男性,女性 ≤ n·m)。 n 和 m 是地图的尺寸​​;雄性和雌性是雄性斯凯奇和雌性斯凯奇的数量。

接下来的 n 行描述了地图。每行包含 m 个字符。特点 '。'代表空闲单元;字符“#”代表有障碍物的单元格。

下一行包含 3 个整数 r、c 和 t (1 ≤ r ≤ n, 1 ≤ c ≤ m, 1 ≤ t ≤ 109):Scaygerboss 的当前坐标以及 Scaygerboss 移动到相邻单元格所需的时间。接下来的雄性行包含雄性 Scayger 的坐标和时间,格式与 Scaygerboss 相同。接下来的雌性行包含雌性 Scayger 的坐标和时间,格式与 Scaygerboss 相同。 (坐标和时间遵循与 Scaygerboss 相同的限制。)所有 Scayger 都居住在没有障碍物的牢房中。

该问题由两个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 F1(14 点)中,约束 1 ≤ n, m ≤ 11 将成立。
- 在子问题 F2(6 点)中,约束 1 ≤ n, m ≤ 22 将成立。

输出

输出使所有 Scayger 看起来既书呆子又可爱所需的最短时间,如果不可能,则输出 -1。

示例

输入 #1

4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2

输出 #1

2

输入 #2

2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2

输出 #2

-1

注意

考虑第一个样本测试。巨龟隐藏在 4 x 4 的地图上。 Scaygerboss 最初驻留在单元格 (2, 1) 中,可以在 1 单位时间内在单元格之间移动。地图上还有 2 只雄性和 3 只雌性斯凯格。其中一只雌性最初位于牢房 (1, 1) 中,所有其他剥壳虫都位于牢房 (2, 1) 中。所有的 Scaygers 在 2 个单位时间内在单元格之间移动。如果 Scaygerboss 和雌性 Scayger 从单元格 (1, 1) 移动到单元格 (1, 2),并且居住在单元格 (2, 1) 中的雄性和雌性 Scayger 移动到单元格 (1, 1),那么所有的 Scaygers 在 2 个单位的时间内都会显得书呆子和可爱。