网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[URAL 1519]一级方程式赛车
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | formula1.in | 输出文件 | formula1.out |
【题目描述】
无论现实情况是什么样的,我们假设Vologda市无法取得20**年冬季奥运会的主办权,众所周知,这个城市将举办F1赛事之一。显然,为了举办这场重要的比赛,宾馆,餐厅,国际机场和一条新的赛道——为了将涌入这座城市的F1粉丝们的需要所有设施——将被修建。但当所有的宾馆和一半的餐厅建成之后,人们发现了一个问题:在赛道的规划位置上有许多地鼠在打洞。因为我们非常喜爱小动物,生态学家们决不会同意在这些洞上修建赛道。因此,市长现在苦恼地坐在他的办公室里,看着标注了所有地鼠洞的赛道规划地图。
谁会足够聪明,来设计一条赛道来避免这座城市的耻辱吗?当然,只有真正的专家——当地蓝翔技校久经沙场的程序员们!但我们的英雄们没有就此满足,而是提出了一个更难的问题:“显然,如果我们找到修筑赛道的方案总数,我们的市长将很自豪!”他们说。
必须要说的是,Vologda市的赛道将会相当简单。赛道将是一条穿过N*M矩形所有网格的单回路。每一段都和某个矩形的边平行,因此弯道都将是直角。在下图中,给出了N=M=4时的两种修筑方案(灰色格子意味着地鼠洞,粗黑线就是赛道)。在下图中没有其他的修建方案。
【输入格式】
输入文件的第一行包含两个正整数N,M(2<=N,M<=12)。
接下来的N行,每行包含M个字符,描述了矩形中相应的网格。字符“.”意味着应当修建赛道的网格,而字符“*”意味着有地鼠打洞的网格。
【输出格式】
输出一行一个正整数,即修筑赛道的方案总数。假设这个数不超过2^63-1。
【样例输入】
sample 1:
4 4
**..
….
….
….
sample 2:
4 4
….
….
….
….
【样例输出】
sample 1:
2
sample 2:
6
【提示】
赛道必须是一条单回路,这意味着赛道不能被分成互不相连的若干个部分。
【来源】
Problem Author: Nikita Rybak, Ilya Grebnov, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge