codeforces 60B
Opened this issue · 0 comments
1.题目链接:
http://codeforces.com/problemset/problem/60/B
2.题面:
3.翻译:
谷物佬的朋友连环佬喜欢看肥皂剧。一集即将开始,他还没有洗盘子。但是他决定至少要在水龙头下放满水。板块可以用平行六面体k×n×m表示,即它有k层(第一层是上一层),每个层都是矩形n×m,带有空正方形('。')和障碍物。 ('#')。水只能存在于空的正方形中。抽头位于第一层的正方形(x,y)上方,可以确保该正方形为空。每分钟有一立方单位的水掉进盘子里。找出连续工作的家伙应该从肥皂剧中解脱多少分钟,然后关掉水,以免注满盘子。就是说,您应该找到盘子绝对装满的时刻,并在下一时刻将被过度填充。
注意:水填满了所有可触及的区域(请参见示例4)。水在1个×1个×1个立方体的面中沿6个方向流动。
输入值
第一行包含三个数字k,n,m(1≤k,n,m≤10),它们是盘子的大小。然后跟随由n行组成的k个矩形,每行包含m个字符“。”。或“#”,按从上到下的顺序代表板的“层”。矩形由空线分隔(请参见示例)。最后一行包含x和y(1≤x≤n,1≤y≤m),它们是抽头的坐标。 x是行号,y是列号。每层的行从左到右用1到n的整数编号,每层的列从上到下用1到m的整数编号。
输出量
答案应包含一个数字,显示盘子将被填充多少分钟。
Examples
input
1 1 1
.
1 1
output
1
input
2 1 1
.
#
1 1
output
1
input
2 2 2
.#
##
..
..
1 1
output
5
input
3 2 2
#.
##
#.
.#
..
..
1 2
output
7
input
3 3 3
.#.
###
##.
.##
###
##.
...
...
...
1 1
output
13
4.思路:
这道题目的基本题意就是你从第一层的某个坐标开始加水,而你的水填满所能流到的位置需要多少时间,流满一个格子需要一分钟,这时候其实就是计算联通的点也多少个,那我们就可以用一个三维数组存图,然后从流入的点开始跑bfs就可以得到总共有多少个联通点,就可以轻易得到答案了
5.参考代码:
#include<bits/stdc++.h>
using namespace std;
char mp[11][11][11];
int k, n, m, x, y, sum = 0;
struct node
{
int x, y, z;
};
queue<node>q;
int dx[11] = {0, 0, 0, 0, -1, 1};
int dy[11] = {0, 0, -1, 1, 0, 0};
int dz[11] = {1, -1, 0, 0, 0, 0};//代表六个方向的数组,上下和前后左右
void bfs()
{
node t;
t.x = x;
t.y = y;
t.z = 1;
q.push(t);//把起点位置存入队列
sum++;、、这时候时间已经加1
mp[1][t.x][t.y] = '#';//已被填充满之后就作为封口
while (!q.empty())
{
int nowx = q.front().x;
int nowy = q.front().y;
int nowz = q.front().z;//调用队首的数据
q.pop();//然后删除队首
for (int i = 0; i < 6; i++)
{
int nextx = nowx + dx[i];
int nexty = nowy + dy[i];
int nextz = nowz + dz[i];//判断六个方向
if (nextx >= 1 && nextx <= n && nexty >= 1 && nexty <= m && nextz >= 1 && nextz <= k)//首先要满足在图的范围内部
{
if (mp[nextz][nextx][nexty] == '.')//如果不是障碍物,并且可以流到
{
t.x = nextx;
t.y = nexty;
t.z = nextz;
q.push(t);//把该点存入队列
sum++;//时间加1
mp[nextz][nextx][nexty] = '#';//已被填充满之后就作为封口
}
}
}
}
}
int main()
{
cin >> k >> n >> m;
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= n; j++)
{
for (int z = 1; z <= m; z++)
{
cin >> mp[i][j][z];
}
}
}
cin >> x >> y;
bfs();
cout << sum ;
}