| 题目名称 | 1972. [HEOI 2015]小Z的房间 |
|---|---|
| 输入输出 | room.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 清羽
于2015-04-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：56， 提交：132， 通过率：42.42% | ||||
 AAAAAAAAAA |
100 | 0.000 s | 0.00 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.002 s | 0.42 MiB | C++ |
 Marvolo |
100 | 0.003 s | 0.55 MiB | C++ |
 stdafx.h |
100 | 0.004 s | 0.39 MiB | C++ |
 _Itachi |
100 | 0.005 s | 0.31 MiB | C++ |
 阿狸 |
100 | 0.005 s | 0.39 MiB | C++ |
 甘罗 |
100 | 0.005 s | 0.55 MiB | C++ |
 神利·代目 |
100 | 0.006 s | 0.33 MiB | C++ |
|
神利·代目 |
100 | 0.006 s | 0.35 MiB | C++ |
 _Horizon |
100 | 0.006 s | 0.92 MiB | C++ |
| 关于 小Z的房间 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
样例没有m
_Itachi
2017-04-12 11:19
2楼
| ||||
|
| ||||
sxysxy-
【问题描述】
你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。
你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。结果对10^9取余。
【输入格式】
从room.in中读入。
第一行两个数分别表示n和m。
接下来n行，每行m个字符，每个字符都会是’.’或者’*’，其中’.’代表房间，’*’代表柱子。
【输出格式】
输出到room.out中。
一行一个整数，表示合法的方案数。
【样例输入1】
2
..
..
【样例输出1】
4
【样例输入2】
2
*.
.*
【样例输出2】
0
【数据规模与约定】
对于前20%的数据，n,m <= 3
对于前50%的数据，n,m <=5
对于前100%的数据，n,m<=9
有40%的数据保证，min(n,m)<=3
有30%的数据保证，不存在柱子