#P17643. [ICPC 2019 Yinchuan R] Xian Xiang
[ICPC 2019 Yinchuan R] Xian Xiang
题目描述
最近几天,Raven 迷上了一款名为“仙乡”的游戏。
游戏开始时,在一个 的矩形区域中散布着一些物品。每个物品拥有 种属性。玩家可以通过一条折线连接任意两个物品来消除它们,该折线的每一段必须是水平或垂直的。然而,这条折线最多只能改变一次方向,且路径上不能有任何物品(该规则类似于“连连看”)。每当物品被消除后,这些物品所在的格子将变为空白,并且会根据被消除的两个物品匹配的属性数目给予一定分数。若两物品间有 个公共属性,得分为 ;若有 个公共属性,得分为 ,……;若有 个公共属性,得分为 。
游戏中有一个记分牌,Raven 迫切地想要登上记分牌的顶端。因此他必须尽己所能获得游戏中的最高分。
输入格式
第一行是一个整数 ,表示测试数据的组数。
每组数据起始于三个正整数 ,分别表示矩形区域的长、宽和每个物品的属性种数。
接下来是 个长度为 的字符串,表示对应的物品。初始时,若格子为空,则该字符串由 个 "-" 组成;若格子中有物品,则该字符串由 个小写字母组成。每个小写字母代表一种属性。如果相连的两个物品在字符串的相同位置上的字母相同,则表明这两个物品在该位置具有相同的属性。
最后一行是 个正整数 。
保证每组数据中的物品数量为偶数且不超过 。
输出格式
对于每组数据,在一行中输出一个整数,表示该局游戏可得的最高可能分数。
3
2 2 3
aaa aaa
bbb bbb
1 10 100 1000
2 3 3
aaa --- bbb
bbb --- aaa
1 10 100 1000
1 4 3
aaa bba abb aaa
1 10 100 1000
2000
2
1010
提示
在第一个样例中,消除第一行和第二行中的两对物品,你将获得 分。
在第二个样例中,由于相同物品无法相连,你只能获得 分。
在第三个样例中,先消除中间的两个物品,再消除最左端和最右端的两个物品。
翻译由 DeepSeek V4 Pro 完成