1322: 地图的四着色

Memory Limit：128 MB Time Limit：4.000 S Judge Style：Text Compare Creator：
Submit：2 Solved：1

Description

有一个R行C列的网格地图，每个国家是一个四连通区域。你的任务是用红、绿、蓝、黄四种颜色给地图着色，使得相邻国家的颜色不同。一个人着色比较无趣，所以你想请女朋友陪你一起涂——你涂红绿，她涂蓝黄。当然，绅士是不会让让女朋友受累的，所以她最多只需涂 5 个国家（恰好 5个也行）。的任务是统计有多少种着色的方法。注意，每个颜色都至少要用一次。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

输入包含不超过 100 组数据。每组数据第一行为两个整数 R 和 C (1<=R,C<=20)，即网格的行数和列数。以 R行每行C个大写字母。相同字母所组成的四连通区域代表一个国家。输入 保证国家数目不超过 30，并且大多数测试点的国家数都比较小。

Output

对于每组数据，输出测试点编号和着色方案数，格式参考样例输出。

Sample Input Copy 

2 4
AABB
BBAA
1 5
ABABA
4 7
AABAABB
ABBCCCB
BBAACBB
CCABBAC

Sample Output Copy 

Case 1: 24
Case 2: 144
Case 3: 3776

Source/Category