网格里的树

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 treeinagrid.in Output file treeinagrid.out

【题目描述】

给你一个r行c列的网格。行被编号为0到r-1,列被编号为0到c-1.第i行第j列的点可以和点(i-1,j),(i,j-1),(i+1,j)和(i,j+1)连边,如果这些点存在。现在,网格中已经有了一些边。你可以向其中添加其他的边。你加边的方式必须使得网格中所有的点都连通,但没有环。你要计算出加边的方案总数。

【输入格式】

输入包含多组数据。

输入文件的第一行是一个整数T(1<=T<=30),即数据组数。

接下来是T组数据。

每组数据的第一行有3个整数r(1<=r<=200),c(1<=c<=8)和md(1<=md<=1000000)。

接下来有2*r-1行,描述了网格和已经添加的边。

每行有2*c-1个字符。

下面,将这些行从0开始编号,将每行的字符也从0开始编号。

偶数行的第偶数个字符将是一个'.',代表一个点。

偶数行的第奇数个字符是一个代表左右两点之间没有边的'S',或是一个代表有边的'-'。

奇数行的第偶数个字符是一个代表上下两点之间没有边的'S',火石一个代表有边的'|'。

奇数行的第计数个字符是一个'S',代表周围四个点围成的空格。

观察样例以更清楚地理解格式。

【输出格式】

对每组数据,输出使所有点连通成一棵树的添边方案总数。这个数有可能很大,因此输出它模md的值。如果没有这样的添边方法,输出一行"Impossible",不含引号。

【样例输入】

6

2 2 1000

.S.

SSS

.S.

2 2 100

.-.

|S|

.S.

2 2 100

.-.

|S|

.-.

3 3 10000

.S.S.

SSSSS

.S.S.

SSSSS

.S.S.

3 3 10000

.-.-.

SSSSS

.-.-.

SSSSS

.-.-.

3 3 10000

.S.S.

|S|S|

.S.S.

|S|S|

.S.S.

【样例输出】

4

1

Impossible

192

9

9

【提示】

为了适应评测机的linux环境,对本题的数据格式进行了修改。在UVa原题中,无边的地方用空格表示,而在这里换成了字符S。

【来源】

UVa11443 Tree in a Grid