1128 : 地图的四着色
时间限制Time Limit
5
秒Sec
内存限制Memory Limit
128
兆MB
提交次数Submitted
41 次Times
通过次数Solved
11 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
题目描述Description
有一个R行C列的网格地图,每个国家是一个四连通区域。你的任务是用红,绿,蓝,黄四种颜色给地图着色,使得相邻国家的颜色不同。
一个人着色比较无趣,所以你想请女朋友陪你一起涂——你涂红绿,她涂蓝黄。当然,绅士是不会让让女朋友受累的,所以她最多只需涂5个国家(恰好5个也行)。
你的任务是统计有多少种着色的方法。注意,每个颜色都至少要用一次。
输入格式Input
输入包含不超过100组数据。每组数据第一行为两个整数R和C (1<=R,C<=20),即网格的行数和列数。以下R行每行C个大写字母。相同字母所组成的四连通区域代表一个国家。输入保证国家数目不超过30,并且大多数测试点的国家数都比较小。
输出格式Output
对于每组数据,输出测试点编号和着色方案数。
样例Sample
出题Author
SRbGa