P17643 [ICPC 2019 Yinchuan R] Xian Xiang

最近几天，Raven 迷上了一款名为“仙乡”的游戏。 游戏开始时，在一个 $n \times m$ 的矩形区域中散布着一些物品。每个物品拥有 $k$ 种属性。玩家可以通过一条折线连接任意两个物品来消除它们，该折线的每一段必须是水平或垂直的。然而，这条折线最多只能改变一次方向，且路径上不能有任何物品（该规则类似于“连连看”）。每当物品被消除后，这些物品所在的格子将变为空白，并且会根据被消除的两个物品匹配的属性数目给予一定分数。若两物品间有 $0$ 个公共属性，得分为 $s_0$；若有 $1$ 个公共属性，得分为 $s_1$，……；若有 $p$ 个公共属性，得分为 $s_p$。 游戏中有一个记分牌，Raven 迫切地想要登上记分牌的顶端。因此他必须尽己所能获得游戏中的最高分。

第一行是一个整数 $T~(1 \le T \le 20)$，表示测试数据的组数。 每组数据起始于三个正整数 $n, m, k~(1 \le n, m \le 7, 1 \le k \le 5)$，分别表示矩形区域的长、宽和每个物品的属性种数。 接下来是 $n \times m$ 个长度为 $k$ 的字符串，表示对应的物品。初始时，若格子为空，则该字符串由 $k$ 个 "-" 组成；若格子中有物品，则该字符串由 $k$ 个小写字母组成。每个小写字母代表一种属性。如果相连的两个物品在字符串的相同位置上的字母相同，则表明这两个物品在该位置具有相同的属性。 最后一行是 $k+1$ 个正整数 $s_0, s_1, \cdots, s_k~(1 \le s_i \le 10000)$。 保证每组数据中的物品数量为偶数且不超过 $18$。

对于每组数据，在一行中输出一个整数，表示该局游戏可得的最高可能分数。

在第一个样例中，消除第一行和第二行中的两对物品，你将获得 $2000$ 分。 在第二个样例中，由于相同物品无法相连，你只能获得 $2$ 分。 在第三个样例中，先消除中间的两个物品，再消除最左端和最右端的两个物品。 翻译由 DeepSeek V4 Pro 完成