#P18309. Travel on the Grid

Travel on the Grid

Travel on the Grid

题目描述

给定一个 N×MN\times M 的网格,你要从 (1,1)(1,1) 到达 (N,M)(N,M)。每次可以移动到周围八个相邻格中的任意一个,不能走出网格。

某些格子有地雷。一颗尚未被中和的地雷会威胁它自身所在的格子及其上、下、左、右四个相邻格;踏入这五个格子中的任意一个都会引爆它。

你可以建造和使用拆雷装置。将装置放在地雷所在格就能中和该地雷。一旦被中和,该地雷以后永远不会爆炸,即使后来装置被取走也一样。 你可以建造多个装置,也可以反复使用同一个装置。

具体规则如下:

  • 当你站在安全格时,可以花费 XX 建造一个装置,并将它放在周围八个相邻格中的一个。安全格是指:该格既没有未被中和的地雷,也不在任何未被中和地雷的攻击范围内。新建装置放到地雷格时会中和地雷。
  • 要重复使用一个已有装置,必须先走到它所在的格子,才能将它取走并携带。取走装置本身没有额外费用。
  • 同一时刻最多携带一个装置。携带时不能建造新装置,也不能拾取另一个装置。
  • 携带装置时,可以花费 YY 将它部署到周围八个相邻格中的一个,目标格必须有地雷。若该地雷尚未被中和,则它被永久中和。不能把携带的装置放到没有地雷的格子。
  • 从 (i,j)(i,j) 移动到相邻格时,若携带着装置,则支付 VijV_{ij};空手移动免费。费用取决于离开的格子。
  • 向相邻格放置装置不是移动,不支付当前格的 VV。新建并放置支付 XX,重复部署已有装置支付 YY。

求到达 (N,M)(N,M) 所需的最小总费用。

保证没有地雷攻击起点 (1,1)(1,1),且没有任何格子同时受到两颗不同地雷的攻击。终点不保证一开始安全。

输入格式

第一行包含正整数 TT,表示测试用例数。

每个测试用例:

  1. 第一行包含 N,M,X,YN,M,X,Y。
  2. 接下来 NN 行,每行是长度为 MM 的字符串。字符 . 表示该格没有地雷,字符 # 表示该格有地雷。没有地雷的格子仍可能处于相邻地雷的攻击范围内。
  3. 接下来 NN 行,每行包含 MM 个整数,第 ii 行第 jj 个整数是 VijV_{ij}。

输出格式

每个测试用例输出一行,表示到达终点的最小费用。

数据范围

  • 1≤T1\le T;
  • 2≤N,M≤10002\le N,M\le1000,N⋅M≤105N\cdot M\le10^5;
  • 1≤X,Y≤1091\le X,Y\le10^9;
  • 0≤Vij≤1090\le V_{ij}\le10^9;
  • 所有测试用例的 N⋅MN\cdot M 之和不超过 10510^5。

攻击范围规则和起点安全保证如题目描述所述。由每个测试用例至少有 44 个格子,可推出 T≤25000T\le25000,这是已有范围的推论。

样例

输入

2
3 4 10 5
....
.#..
...#
0 0 0 0
0 1 2 3
0 0 0 0
3 4 10 10
..#.
....
#..#
0 0 1 0
0 0 0 0
1 0 0 0

输出

16
20

说明

第一例:

  1. 在 (1,1)(1,1) 花费 1010 新建装置,放到 (2,2)(2,2) 并中和地雷。
  2. 走到 (2,2)(2,2),取走装置。
  3. 携带装置从 (2,2)(2,2) 移到 (2,3)(2,3),支付 V2,2=1V_{2,2}=1。
  4. 花费 55 将装置部署到 (3,4)(3,4),中和地雷。此时不需要支付 V2,3=2V_{2,3}=2。
  5. 走到 (3,4)(3,4) 即可到达终点。

总费用为 10+1+5=1610+1+5=16。

第二例可以先走到 (2,2)(2,2),花费 1010 新建装置并放到 (1,3)(1,3)。然后空手走到 (2,3)(2,3),再花费 1010 新建另一个装置并放到 (3,4)(3,4),最后到达终点,总费用为 2020。如果试图重复使用装置,至少要携带它移动一步,总费用至少为 2121。