CSG-CPC
Online Judge

1128 : 地图的四着色

         Time Limit: 5 Sec     Memory Limit: 128 Mb     Submitted: 46     Solved: 11    

Description

有一个R行C列的网格地图,每个国家是一个四连通区域。你的任务是用红,绿,蓝,黄四种颜色给地图着色,使得相邻国家的颜色不同。

一个人着色比较无趣,所以你想请女朋友陪你一起涂——你涂红绿,她涂蓝黄。当然,绅士是不会让让女朋友受累的,所以她最多只需涂5个国家(恰好5个也行)。

你的任务是统计有多少种着色的方法。注意,每个颜色都至少要用一次。

Input

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

Output

对于每组数据,输出测试点编号和着色方案数。

Sample

2 4
AABB
BBAA
1 5
ABABA
4 7
AABAABB
ABBCCCB
BBAACBB
CCABBAC
Case 1: 24
Case 2: 144
Case 3: 3776

Hint

Author

SRbGa