【试题来源】
2011中国国家集训队命题答辩
【问题描述】
有N行M列的点组成一个点阵。你通过用水平和竖直的线段连接一些相邻的点画若干闭合的回路,将所有的点连接起来,组成一个图形。连的线被视为是内部和外部的界限。其中,有一些点(用*和#表示)不用被连接,且用*表示的点在必须在图形内部,用#表示的点必须在图形外部。
例如:(用+表示点,-和|表示线,x表示图形内部)
以及
注意:这个点是在外部!
你要写一个程序来计算一共有多少种连线的方法。我们只关心它模一个大质数123456791的余数。
例如:(用+表示点,-和|表示线,x表示图形内部)
以及
注意:这个点是在外部!
你要写一个程序来计算一共有多少种连线的方法。我们只关心它模一个大质数123456791的余数。
【输入格式】
输入的第一行包含两个正整数,分别表示行数N和列数M。
接下来N行,每行M个字符表示点的情况(用.*#来表示三种点)。
50%的数据满足:
总的方法数小于220000
100%的数据满足:
M≤12,N≤20
接下来N行,每行M个字符表示点的情况(用.*#来表示三种点)。
50%的数据满足:
总的方法数小于220000
100%的数据满足:
M≤12,N≤20
【输出格式】
输出一个整数,表示总方法数模123456791的余数。
【样例输入】
5 6
......
....*.
..#...
......
......
......
....*.
..#...
......
......
【样例输出】
117