#P2518. Little guys' game

    ID: 1519 传统题 1000ms 256MiB 尝试: 1 已通过: 0 难度: 10 上传者: 标签>搜索枚举数据结构POJ Monthly--2005.07.31Huang Ninghai

Little guys' game

题目描述

有一群小朋友在玩一个游戏。游戏在一个 4×44 \times 4 的方格中进行,方格中填有字符 'A''B''C''D',每种字符恰好出现 44 次。玩家可以任意交换相邻的字符(水平或垂直相邻)。游戏开始时,玩家需要选择一个目标字符(从 'A''B''C''D' 中选),当任意一个 2×22 \times 2 的子方格中所有字符都与玩家选择的目标字符相同时,玩家获胜。

小朋友们希望用最少的交换次数赢得游戏。现在他们向你求助,你能帮他们吗?

输入格式

输入包含多个测试用例。每个测试用例包含一个 4×44 \times 4 的方格,表示初始状态。注意方格中只包含 'A''B''C''D',且每种字符恰好出现 44 次。

输出格式

对于每个测试用例,输出两个整数:

  1. 赢得游戏所需的最少交换次数。
  2. 能够实现最少交换次数的策略种类数。

注意:如果两种策略的交换顺序相同但选择的目标字符不同,这两种策略仍被视为不同的策略。

输入样例 1

AABB
ABAB
CDCD
CCDD

ACAB
CBBD
ADAD
DCBC

输出样例 1

1 4
4 96

来源

POJ Monthly--2005.07.31, Huang Ninghai