WishingBone plans to decorate his hexagon-shaped room with unique flooring patterns. First he divides it into triangles, and colors them with different colors. Now that he has got a satisfactory pattern, he uses small rugs to cover the floor. The rugs sold at shops are diamond-shaped; exact the shape of two adjacent triangles. He is not willing to cut any of them. Different colored rugs are labeled different price. And he does care about the price - he cares about the most expensive rugs that he should use to finish the covering. Input There are multiple tests, for each test: The first line is an integer specifying the side of his room (1 <= n <= 50). The following 2n lines with the pattern of the room, with upper-case letters denoting different colors. So there are at most 26 colors. Since the room is considerably large and sometimes needs pillars to support the ceiling, some triangles are marked with '.' rather than a letter. Such triangles are not to be covered. The following line contains one integer m (1 <= m <= 351) - number of rugs in the shop. The following m lines contains one type of rug (with two upper-case letters) and its price p (1 <= p <= 100000). There will not be duplicate items listed, that is, if AB is listed, BA will not appear. You may assume the number of each type to be infinite. Output One line for each test, the price of the most expensive rugs used. Of course, you have to minimize this value. If there is no solution to the problem, print a 0.

这是一道动态规划问题。我们可以把每个菱形看做一个节点，节点之间有边相连，边的权值为两个节点对应的三角形的颜色组合。我们需要找到一条路径，使得路径上所有边的权值之和最小，且路径经过的所有节点组成的集合覆盖了所有的三角形。这可以通过最小权闭合子图来求解。具体来说，我们可以在原图上添加一个超级源点和一个超级汇点，然后把所有未被覆盖的三角形对应的节点与源点相连，把所有已经被覆盖的三角形对应的节点与汇点相连，然后在新图上求解最小权闭合子图即可。如果闭合子图不存在，则说明无法完全覆盖所有三角形，输出0。

对于每个测试用例，可以按照以下步骤求解：

1. 构建图，计算每个三角形对应的节点编号和对应的菱形编号。
2. 构建新图，添加超级源点和超级汇点，并按照上述方法连接节点和超级源点/超级汇点。
3. 在新图上求解最小权闭合子图，得到路径上所有边的权值之和。
4. 如果闭合子图不存在，则输出0；否则输出路径上所有边的权值之和。

时间复杂度为 O(n^3)，可以通过本题。

相关问题

WishingBone's Room Plan

"WishingBone's Room Plan"是一道图论题目，需要使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。题目描述如下：

题目描述：

WishingBone 喜欢高耸的大楼，这次他要去参观一栋大楼。这栋大楼有n个房间，房间之间有m条通道连接。WishingBone 想知道从任意一个房间出发，最多可以到达多少个房间以及可以到达哪些房间。

输入格式：

第一行包含两个整数n和m，表示房间数和通道数。

接下来m行，每行包含两个整数a和b，表示房间a和房间b之间有一条通道。

输出格式：

输出n行，每行包含两个整数，第i行表示从第i个房间出发，最多可以到达多少个房间以及可以到达哪些房间。其中，第一个数表示最多可以到达的房间数，第二个数表示可以到达的房间编号，按照从小到大的顺序输出。

解题思路：

可以使用DFS或BFS来解决本题。以DFS为例，具体实现步骤如下：

1. 构建邻接表，表示房间之间的通道关系。

2. 初始化visited数组，表示每个房间是否被访问过。

3. 对于每个房间i，进行DFS遍历，记录可以到达的房间数和可以到达的房间编号。

4. DFS遍历过程中，对于当前房间i，将visited[i]标记为已访问，并遍历与该房间相邻的未访问过的房间j。对于每个相邻房间j，递归进行DFS遍历。

5. 当遍历完所有相邻的房间后，将visited[i]重置为未访问。

6. 对于每个房间i，输出可以到达的房间数和可以到达的房间编号，按照从小到大的顺序输出。

需要注意的是，对于本题，DFS和BFS的实现思路是一样的，只是遍历顺序不同。DFS是采用深度优先的方式遍历，而BFS是采用广度优先的方式遍历。