1128 : 地图的四着色
Time Limit: 5 Sec Memory Limit: 128 Mb Submitted: 46 Solved: 11Description
有一个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