P74180

打通蚁穴

难度 4 级 小学 算法入门 BFS 搜索
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

小明想要观察两个蚁群的战斗。他有很大的一块观察蚂蚁工坊。

我们从长 、宽、深三个维度把蚂蚁工坊其划分为若干正立方体。其中有一些是蚁穴,有一些是普通的土地。

如果两个立方体上下、左右、前后相邻,那么它们是属于同一个蚁穴的,一个蚁穴内生活着一群蚂蚁,不同的蚁穴属于不同的族群。

现在小明想要知道,他挖空多少单位立方体的蚁穴,可以使得两条不同的蚁穴连通

输入

第一行一个数字n表示土地的单位长、宽、高

接下来n段,每段n行,每行n个0或1,0表示土地,1表示蚁穴

输出

仅一个数字,小明需要挖的蚁穴大小

样例

样例 1
输入
2
0 1
1 0

1 0
0 1
输出
1
样例 2
输入
4
1 0 0 0 
0 0 0 0 
0 1 0 0 
0 0 0 0 

0 0 0 0 
0 0 0 0 
0 1 0 0 
0 0 1 0 

0 0 0 0 
0 0 0 0 
1 1 1 0 
0 0 1 0 

0 0 1 0 
0 1 0 0 
0 1 1 0 
1 0 0 0
输出
2

提示

n \leq 30

保证至少有两个蚁穴

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交