CF60B Serial Time! 解题报告
1 题目链接
http://codeforces.com/problemset/problem/60/B
2 题目整理
题目 ：连续剧时间！
题目描述
锡里尔的朋友们喜欢看电视连续剧剧。一集就要开始了，他还没有洗盘子。但他决定至少在水龙头下放满水。板可以用一个平行六面体k ?×? n ?×? m表示，即它有k层（第一层是上一层），每一层都是一个长方形n ?×? m，有空方格（’.’）和障碍物(’#’)。水只能出现在空旷的方格中。抽头位于正方形上方( x ,? y )第一层，保证这个方格是空的。每分钟就有一个立方单位的水落入盘子。找出连环男演员应该在多少分钟内将自己从肥皂剧中解脱出来，然后关掉水，以免盘子溢出。也就是说，您应该找到盘子绝对装满并且下一刻将被装满的时刻。
注意：水会填满触手可及的所有区域（参见示例 4）。水在 6 个方向中的每一个方向上流动，通过1 × 1 × 1立方体的面。
输入格式
第一行包含三个数字k、n、m，它们是板的尺寸。然后沿着由n行组成的k个矩形，每行包含m个字符’或者“#”，它代表盘子的“层”，顺序是从上到下。矩形之间用空线隔开（参见示例）。最后一行包含抽头的坐标x和y。x是行的编号，y是列的编号。每层的行从左到右用1到n的整数编号，每层的列从上到下用1到m的整数编号。
输出格式
答案应该包含一个数字，显示盘子将在多少分钟内填满。
样例输入1
1 1 1.1 1
样例输出1
1
样例输入2
2 1 1.#1 1
样例输出2
1
样例输入3
2 2 2.#
##..
..1 1
样例输出3
5
样例输入4
3 2 2#.
###.
.#..
..1 2
样例输出4
7
样例输入5
3 3 3.#.
###
##..##
###
##....
...
...1 1
样例输出5
13
数据范围
对于 100 % 100\% 100%的数据:
1 ≤ n , m ， k ≤ 10 1 \le n, m，k \le 10 1≤n,m，k≤10
1 ≤ x ≤ n 1 \le x \le n 1≤x≤n
1 ≤ y ≤ m 1 \le y \le m 1≤y≤m
3 题意分析
3.1 题目大意
给定一个三维空间，问（x, y, 1）所在的联通块有多少个小单元格？
3.2 样例分析
如上所述。
4 解法分析
这道题，其实和走迷宫问题很像，只不过是把地图升级成了三维的而已。此题深搜广搜都能做。
深搜就是把可能的路径都试一遍，发现到了一个没走过的格子就把答案+1,时间复杂度会比较高(但这题范围小，
能过）。
广搜每一次都扩展一些点，如果扩展的点不能走或者走过了，就不走；否则加进队列，答案+1,时间复杂度O(nm
k)，肯定能过。
AC代码
ACCode #001
// From Heart_Blue
// Rating 2425
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e2 + 10;
char board[N][N][N];
int flag[N][N][N];
int dx[] = {
0,0,0,0,1,-1 };
int dy[] = {
0,0,1,-1,0,0 };
int dz[] = {
1,-1,0,0,0,0 };
int k, n, m;
int ans = 0;
void dfs(int x, int y, int z)
{
if (x < 0 || x == k) return;if (y < 0 || y == n) return;if (z < 0 || z == m) return;if (flag[x][y][z]) return;if (board[x][y][z] == '#') return;flag[x][y][z] = 1;ans++;for (int i = 0; i < 6; i++){
dfs(x + dx[i], y + dy[i], z + dz[i]);}
}
int main()
{
//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);cin >> k >> n >> m;for (int i = 0; i < k; i++){
for (int j = 0; j < n; j++){
cin >> board[i][j];}}int x, y;cin >> x >> y;dfs(0, x - 1, y - 1);cout << ans << endl;return 0;
}
ACCode #002
// From abdulla.ashraf
// Rating 1939
#include <bits/stdc++.h>using namespace std;typedef long long ll;int OO = 1000000000;char g[15][15][15];int n, m, k;int go(int x, int y, int z) {
if (x < 0 || y < 0 || z < 0 || x >= n || y >= m || z >= k|| g[x][y][z] == '#')return 0;g[x][y][z] = '#';int ret = 1;ret += go(x + 1, y, z);ret += go(x - 1, y, z);ret += go(x, y + 1, z);ret += go(x, y - 1, z);ret += go(x, y, z + 1);ret += go(x, y, z - 1);return ret;
}int main() {
int x, y;cin >> k >> n >> m;for (int i = 0; i < k; i++)for (int j = 0; j < n; j++)for (int h = 0; h < m; h++)cin >> g[j][h][i];cin >> x >> y;cout << go(x-1,y-1,0);return 0;
}
ACCode #003
// From KieranHorgan
// Rating 2190
#include <bits/stdc++.h>#define ll long longusing namespace std;ll n, m, l, ans;
vector<int> a;
string s;
bool visited[11][11][11];int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cin >> l >> n >> m;for(int i = 0; i < l; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < m; k++) {
char c;cin >> c;if(c=='#') visited[i][j][k] = 1;}}}int t1, t2;cin >> t1 >> t2;t1--;t2--;queue<pair<int,pair<int,int>>> q;q.push({
0,{
t1,t2}});while(!q.empty()) {
pair<int, pair<int, int>> u = q.front();q.pop();int x = u.second.first;int y = u.second.second;int z = u.first;
// cout << z << " " << x << " " << y << endl;if(x<0||x>=n || y<0||y>=m || z<0||z>=l || visited[z][x][y]) {
continue;}visited[z][x][y] = 1;ans++;q.push({
z+1,{
x,y}});q.push({
z-1,{
x,y}});q.push({
z,{
x+1,y}});q.push({
z,{
x-1,y}});q.push({
z,{
x,y+1}});q.push({
z,{
x,y-1}});}cout << ans << endl;
}