OI题库

【题目描述】

给你一个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