#D0928. 仓库货位

仓库货位

题目描述

仓库分成 k×n×mk\times n\times m 个货位,每个货位用坐标 (x,y,z)(x,y,z) 表示,其中 1xk1\le x\le k1yn1\le y\le n1zm1\le z\le m。搬运机器人只能把货物从 (x,y,z)(x,y,z) 运到 (x+1,y,z)(x+1,y,z)(x,y+1,z)(x,y+1,z)(x,y,z+1)(x,y,z+1),不能反方向移动。有些货位被占用,机器人不能进入,称为无效货位;其余货位称为有效货位。如果一个有效货位能经过若干有效货位到达另一个有效货位,就说它们之间可以到达。

货位 ZZ 被称为“关键货位”,当且仅当存在两个互不相同的有效货位 X,YX,Y,满足:

  • X,Y,ZX,Y,Z 三者互不相同;
  • XX 能到达 YY
  • 如果把 ZZ 改成无效货位,XX 就无法到达 YY

请统计仓库中关键货位的数量。

输入格式

第一行三个正整数 k,n,mk,n,m

接下来依次给出 kk 块,每块 nn 行,每行一个长度为 mm 的 01 串,描述该层货位是否有效,其中 1 表示有效,0 表示无效。

输出格式

输出一个整数,表示关键货位的数量。

样例

1 2 3
111
111
2
2 2 2
11
11
10
11
2
3 1 1
1
1
1
1

样例解释

样例 1 中,沿着 zz 方向的两行各有一个中间货位,它们分别是本行两端货位之间的必经点,共 22 个关键货位。

样例 2 中,有一个货位被占用,剩下只有 22 个货位会成为必经点。

样例 3 是一条三个货位的链,中间那个是关键货位。

数据范围与约定

子任务 分值 限制
11 3030 k=n=1k=n=11m1001\le m\le 100
22 knm60k\cdot n\cdot m\le 60
33 4040 1k,n,m1001\le k,n,m\le 100

对于 100%100\% 的数据,1k,n,m1001\le k,n,m\le 100,字符串只包含 01