#P2518. Little guys' game
Little guys' game
题目描述
有一群小朋友在玩一个游戏。游戏在一个 的方格中进行,方格中填有字符 'A'
、'B'
、'C'
和 'D'
,每种字符恰好出现 次。玩家可以任意交换相邻的字符(水平或垂直相邻)。游戏开始时,玩家需要选择一个目标字符(从 'A'
、'B'
、'C'
和 'D'
中选),当任意一个 的子方格中所有字符都与玩家选择的目标字符相同时,玩家获胜。
小朋友们希望用最少的交换次数赢得游戏。现在他们向你求助,你能帮他们吗?
输入格式
输入包含多个测试用例。每个测试用例包含一个 的方格,表示初始状态。注意方格中只包含 'A'
、'B'
、'C'
和 'D'
,且每种字符恰好出现 次。
输出格式
对于每个测试用例,输出两个整数:
- 赢得游戏所需的最少交换次数。
- 能够实现最少交换次数的策略种类数。
注意:如果两种策略的交换顺序相同但选择的目标字符不同,这两种策略仍被视为不同的策略。
输入样例 1
AABB
ABAB
CDCD
CCDD
ACAB
CBBD
ADAD
DCBC
输出样例 1
1 4
4 96
来源
POJ Monthly--2005.07.31, Huang Ninghai