#P18309. Travel on the Grid
Travel on the Grid
Travel on the Grid
题目描述
给定一个 的网格,你要从 到达 。每次可以移动到周围八个相邻格中的任意一个,不能走出网格。
某些格子有地雷。一颗尚未被中和的地雷会威胁它自身所在的格子及其上、下、左、右四个相邻格;踏入这五个格子中的任意一个都会引爆它。
你可以建造和使用拆雷装置。将装置放在地雷所在格就能中和该地雷。一旦被中和,该地雷以后永远不会爆炸,即使后来装置被取走也一样。 你可以建造多个装置,也可以反复使用同一个装置。
具体规则如下:
- 当你站在安全格时,可以花费 建造一个装置,并将它放在周围八个相邻格中的一个。安全格是指:该格既没有未被中和的地雷,也不在任何未被中和地雷的攻击范围内。新建装置放到地雷格时会中和地雷。
- 要重复使用一个已有装置,必须先走到它所在的格子,才能将它取走并携带。取走装置本身没有额外费用。
- 同一时刻最多携带一个装置。携带时不能建造新装置,也不能拾取另一个装置。
- 携带装置时,可以花费 将它部署到周围八个相邻格中的一个,目标格必须有地雷。若该地雷尚未被中和,则它被永久中和。不能把携带的装置放到没有地雷的格子。
- 从 移动到相邻格时,若携带着装置,则支付 ;空手移动免费。费用取决于离开的格子。
- 向相邻格放置装置不是移动,不支付当前格的 。新建并放置支付 ,重复部署已有装置支付 。
求到达 所需的最小总费用。
保证没有地雷攻击起点 ,且没有任何格子同时受到两颗不同地雷的攻击。终点不保证一开始安全。
输入格式
第一行包含正整数 ,表示测试用例数。
每个测试用例:
- 第一行包含 。
- 接下来 行,每行是长度为 的字符串。字符
.表示该格没有地雷,字符#表示该格有地雷。没有地雷的格子仍可能处于相邻地雷的攻击范围内。 - 接下来 行,每行包含 个整数,第 行第 个整数是 。
输出格式
每个测试用例输出一行,表示到达终点的最小费用。
数据范围
- ;
- ,;
- ;
- ;
- 所有测试用例的 之和不超过 。
攻击范围规则和起点安全保证如题目描述所述。由每个测试用例至少有 个格子,可推出 ,这是已有范围的推论。
样例
输入
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
说明
第一例:
- 在 花费 新建装置,放到 并中和地雷。
- 走到 ,取走装置。
- 携带装置从 移到 ,支付 。
- 花费 将装置部署到 ,中和地雷。此时不需要支付 。
- 走到 即可到达终点。
总费用为 。
第二例可以先走到 ,花费 新建装置并放到 。然后空手走到 ,再花费 新建另一个装置并放到 ,最后到达终点,总费用为 。如果试图重复使用装置,至少要携带它移动一步,总费用至少为 。