#D0928. 仓库货位
仓库货位
题目描述
仓库分成 个货位,每个货位用坐标 表示,其中 ,,。搬运机器人只能把货物从 运到 、、,不能反方向移动。有些货位被占用,机器人不能进入,称为无效货位;其余货位称为有效货位。如果一个有效货位能经过若干有效货位到达另一个有效货位,就说它们之间可以到达。
货位 被称为“关键货位”,当且仅当存在两个互不相同的有效货位 ,满足:
- 三者互不相同;
- 能到达 ;
- 如果把 改成无效货位, 就无法到达 。
请统计仓库中关键货位的数量。
输入格式
第一行三个正整数 。
接下来依次给出 块,每块 行,每行一个长度为 的 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 中,沿着 方向的两行各有一个中间货位,它们分别是本行两端货位之间的必经点,共 个关键货位。
样例 2 中,有一个货位被占用,剩下只有 个货位会成为必经点。
样例 3 是一条三个货位的链,中间那个是关键货位。
数据范围与约定
| 子任务 | 分值 | 限制 |
|---|---|---|
| , | ||
对于 的数据,,字符串只包含 0 和 1。