CF1611G Robot and Candies

Polycarp 有一个 $n \times m$ 的矩形田地（田地的总格数 $n \cdot m$ 不超过 $10^6$，且 $m \ge 2$），每个格子里可能有糖果。田地有 $n$ 行 $m$ 列。 我们用 $(x, y)$ 表示第 $x$ 行第 $y$ 列的格子。左上角的格子为 $(1, 1)$，右下角的格子为 $(n, m)$。 如果某格子有糖果，则用符号 '1' 标记，否则用符号 '0' 标记。 Polycarp 制作了一个可以收集糖果的机器人。机器人可以从 $(x, y)$ 移动到 $(x+1, y+1)$ 或 $(x+1, y-1)$。如果机器人所在的格子有糖果，则会收集该糖果。 只要田地上还有糖果，Polycarp 就会执行如下操作： - Polycarp 将机器人放在田地最上面一行的任意一个格子中。他可以自行选择放置的位置。允许多次将机器人放在同一个格子。 - 机器人在田地中移动并收集糖果。Polycarp 控制机器人的移动。 - 当机器人离开田地后，Polycarp 会取回机器人。如果田地上还有糖果，Polycarp 会重复上述过程。 请你计算，Polycarp 至少需要多少次将机器人放在田地最上面一行，才能收集完所有糖果。保证 Polycarp 总能收集完所有糖果。

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示数据组数。 每组数据前有一个空行。接下来一行包含两个整数 $n$ 和 $m$（$2 \le m$，$2 \le n \cdot m \le 10^6$），表示田地的大小。接下来有 $n$ 行，第 $i$ 行是一个长度为 $m$ 的字符串，描述第 $i$ 行的田地。'1' 表示该格有糖果，'0' 表示该格为空。 保证所有数据组的 $n \cdot m$ 之和不超过 $10^6$。

输出 $t$ 行，每行一个整数，表示对应数据组 Polycarp 至少需要多少次将机器人放在田地最上面一行，才能收集完所有糖果。

在第一组数据中，Polycarp 可以不需要放置机器人，因此答案是“0”。 在第二组数据中，Polycarp 需要放置机器人两次。第一次可以将机器人放在 $(1, 1)$，收集 $(1, 1)$ 和 $(3, 3)$ 的糖果。第二次再次放在 $(1, 1)$，机器人可以先移动到 $(2, 2)$，再到 $(3, 1)$，收集最后一个糖果。 在第四组数据中，可以证明机器人无法在三次内收集完所有糖果。 由 ChatGPT 4.1 翻译