← 返回题目列表

Codeforces · 1611/G

G. 机器人和糖果

中文机器翻译题面 查看原题

Polycarp 有一个由 $$$n \times m$$$ 个单元组成的矩形区域($$$n \cdot m$$$ 区域的大小不超过 $$$10^6$$$ 单元,$$$m \ge 2$$$),每个单元中都可以有糖果。该字段中有 $$$n$$$ 行和 $$$m$$$ 列。

让我们用 $$$(x, y)$$$ 表示一个垂直坐标为 $$$x$$$ 水平坐标为 $$$y$$$ 的单元格。那么左上角的单元格将表示为 $$$(1, 1)$$$,右下角的单元格将表示为 $$$(n, m)$$$。

如果单元格中有糖果,则该单元格标记为符号“1”,否则 — 标记为符号“0”。

波利卡普制作了一个可以收集糖果的机器人。机器人可以从 $$$(x, y)$$$ 移动到 $$$(x+1, y+1)$$$ 或 $$$(x+1, y-1)$$$。如果机器人位于装有糖果的牢房中,它就会拿走它。

当场上至少有一颗糖果时,执行以下过程:

- Polycarp 将机器人放置在场地最顶行的任意单元格中。他自己选择将机器人放置在哪个牢房中。允许将机器人多次放置在同一个牢房中。
- 机器人穿过场地并收集糖果。他控制着机器人。
- 当机器人离开场地时,波利卡普将其带走。如果还剩下糖果,波利卡普会重复这个过程。

求波利卡普需要将机器人放在场地最上面一排才能收集到所有糖果的最少次数。保证波利卡普总能收集到所有糖果。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中输入数据集的数量。

在每个输入数据之前,测试中有一个空行。接下来是包含整数 $$$n$$$ 和 $$$m$$$ 的行 ($$$2 \le m$$$, $$$2 \le n \cdot m \le 10^6$$$) — 字段大小。接下来是 $$$n$$$ 行,其中 $$$i$$$ 描述了字段的第 $$$i$$$ 行。它们每个都是一个大小为 $$$m$$$ 个字符的字符串:符号“1”对应于带有糖果的单元格,符号“0”对应于空单元格。

保证测试中所有输入数据集的 $$$n \cdot m$$$ 值的总和不超过 $$$10^6$$$。

输出

打印 $$$t$$$ 行,每行应包含相应输入数据集的答案:Polycarpus 需要将机器人放在场地最上面一行才能收集所有糖果的最少次数。

示例

输入 #1

4

2 2
00
00

3 3
100
000
101

4 5
01000
00001
00010
10000

3 3
111
111
111

输出 #1

0
2
2
4

注意

在第一盘波利卡普可能根本不会将机器人放到场上,所以答案“0”

在第二盘中,Polycarp 需要将机器人放置在场地上两次。机器人可以这样收集糖果:Polycarp 第一次将机器人放入单元格 $$$(1, 1)$$$ 中,并在 $$$(1, 1)$$$ 和 $$$(3, 3)$$$ 位置收集糖果。第二次Polycarp可以再次将机器人放入$$$(1, 1)$$$,然后机器人将首先移动到$$$(2,2)$$$,然后移动到$$$(3, 1)$$$并收集最后一颗糖果。

在第四组中,您可以证明机器人无法在三遍中收集到所有糖果。