| 题目名称 | 1525. [UVa 11443] 网格里的树 |
|---|---|
| 输入输出 | treeinagrid.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 3 |
| 题目来源 |
 cstdio
于2014-02-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：2， 通过率：100% | ||||
 FoolMike |
100 | 1.056 s | 9.55 MiB | C++ |
 cstdio |
100 | 1.759 s | 9.56 MiB | C++ |
| 关于 网格里的树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
输入问题搞了半天……用getline的尝试失败了……
| ||||
【题目描述】
给你一个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。