[URAL 1519]一级方程式赛车

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file formula1.in Output file 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

URAL 1519 Formula 1