沙漠之王，也就是林克的宿敌加农多夫，已经知道了这位英雄疯狂收集心碎片的行为，而这与他的邪恶计划几乎不相符。为了阻止英雄前进，邪恶的国王亲自进入失落的森林，在林克得到它们之前收集心脏碎片。

这个链接(1)包含一个zip文件，用单个文件输入格式指定为这个100个迷宫的问题集合。

• 林克和加农多夫在树林中的不同位置开始，林克是“L”，而加农多夫是“G”。
• 林克可以先移动，迈出一步，也可以选择保持静止。如果他触碰了一块未收集的心块，它就会永久归他所有。
• 加农多夫下一步行动，迈出了一步，如果他愿意，也可以保持不动。如果他触碰了一个未收集的心脏碎片，它就会永久地成为他的，并且林克永远无法收集它。
• 这个过程会重复，直到Link无法收集更多的心脏碎片。
• 当然，Ganondorf是一个完美的逻辑学家，他会选择最优的步骤，以减少Link能够收集到的心脏碎片的数量。

让 $年代$是每个迷宫得分的和。我们将分数定义为迷宫指数(基于1)乘以Link在Ganondorf干扰下能够收集到的最大Heart Pieces数量。

找到 $\盒装{年代}$．

---

例子:

输入:

4 5 5 ##。# # . . G . .H###H .###. . l ..5 5 ## l ## .....H###H .###. . g ..5 5 ##。# # . . G . .H #。# h .#.#. . l .. .7 4 ## l。G## h .#.#. h #.....# # # # . h

输出:

13

输出解释道:

在第一个迷宫中，Ganondorf可以无限地模仿林克的左右移动，直到他靠近一个Heart Piece，然后他可以在林克之前收集到这个Heart Piece，然后在林克之前获取第二个Heart Piece。虽然林克可以无限期地延长开始时间，但无论如何他都不会收集到一个心脏碎片，所以这个迷宫的分数是 $0$．

在第二个迷宫中，Link和Ganondorf的位置与第一个迷宫相反，Link后退了一个空间以弥补第一个回合的优势。尽管如此，林克不能采用与加农多夫相同的策略——如果他这么做了，加农多夫就可以无限期地坐着不动，而林克永远不会收集到心块，这是加农多夫的最佳最终结果。因此，林克必须牺牲一个心块给加农多夫，去追逐另一个心块，为这个迷宫创造分数 $1$乘以下标。

在第三个迷宫中，情况与第一个迷宫相似，但现在Link有了一个新的方法。尽管通往每个Heart Piece的中间路径要比通往两侧的路径长，但通过走中间环节，Ganondorf不得不选择一个Heart Piece来防守，牺牲另一个环节，从而为迷宫创造分数 $1$乘以下标。

在第四个迷宫中，Link与所有四个Heart Pieces的距离是相等的，与Ganondorf一样，所以凭借第一个回合优势，他至少可以获得一个。然而，无论加农多夫走哪条路，如果他对加农多夫的动作做出正确的反应，林克都可以得到第二个心形碎片，但不会得到第三个。这个迷宫的分数是这样的 $2$乘以下标。

$1 \ * 0 + 2 \ * 1 + 3 \ * 1 + 4 \ * 2 = 13$

---

细节:

• Link总是会在每个迷宫中以L的形式出现一次。
• 每个迷宫中，加农多夫总是以“G”的形式出现一次。
• 每个迷宫最多有5个心块，如“H”。
• 开阔地用'.'表示。
• 不可穿透的树以“#”表示。
• 每个迷宫中不会出现其他角色。
• Ganondorf是最佳玩法，明确目标是最小化Link收集的Heart Pieces数量。两个角色在任何时候都拥有完美的信息。
• 林克和加农多夫可以自由穿过对方。

• $W * H * leq 30$在所有的迷宫里。

  (1) -此链接目前指向我的Dropbox帐户，因为目前没有办法将非图像内容上传到Brilliant。管理员，如果有更改，请随意删除此脚注。

---

这是一本叫做失落的森林， CS /图论中的一系列问题。

---

图片来源:http://zelda.wikia.com/wiki/Ganondorf