AT_abc291_f [ABC291F] Teleporter and Closed off

题目描述

有 $N$ 个城市，编号为城市 $1$、城市 $2$、$\ldots$、城市 $N$。
有一些不同城市之间可以通过单向传送器进行移动。对于每个城市 $i$（$1\leq i\leq N$），可以通过长度为 $M$ 的仅由 0 和 1 组成的字符串 $S_i$ 来表示城市 $i$ 通过传送器可以直接到达的城市。具体来说，对于 $1\leq j\leq N$：

• 如果 $1\leq j-i\leq M$ 且 $S_i$ 的第 $j-i$ 个字符为 1，则可以从城市 $i$ 直接移动到城市 $j$。
• 否则，不能从城市 $i$ 直接移动到城市 $j$。

对于 $k=2,3,\ldots,N-1$，请解决以下问题：

通过重复使用传送器，不经过城市 $k$，能否从城市 $1$ 移动到城市 $N$？如果可以，请输出所需传送器使用次数的最小值；如果不可以，输出 $-1$。

输入格式

输入以以下格式从标准输入给出。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

请将 $N-2$ 个整数以空格分隔输出在一行。第 $i$（$1\leq i\leq N-2$）个数为对应 $k=i+1$ 的问题答案。

输入输出样例 #1

输入 #1

5 2
11
01
11
10
00

输出 #1

2 3 2

输入输出样例 #2

输入 #2

6 3
101
001
101
000
100
000

输出 #2

-1 3 3 -1

说明/提示

限制条件

• $3\leq N\leq 10^5$
• $1\leq M\leq 10$
• $M<N$
• $S_i$ 是仅由 0 和 1 组成的长度为 $M$ 的字符串
• 若 $i+j>N$，则 $S_i$ 的第 $j$ 个字符为 0
• $N,M$ 为整数

样例解释 1

通过传送器，每个城市可以直接到达以下城市：

• 城市 $1$ 可以到达城市 $2,3$。
• 城市 $2$ 可以到达城市 $4$。
• 城市 $3$ 可以到达城市 $4,5$。
• 城市 $4$ 可以到达城市 $5$。
• 城市 $5$ 无法到达其它城市。

因此，从城市 $1$ 到城市 $5$ 的路径有：

• 路径 $1$：城市 $1\to 2\to 4\to 5$
• 路径 $2$：城市 $1\to 3\to 4\to 5$
• 路径 $3$：城市 $1\to 3\to 5$

不经过城市 $2$ 的路径有路径 $2$ 和路径 $3$，其中最少使用传送器次数的是路径 $3$，共 $2$ 次。 不经过城市 $3$ 的路径只有路径 $1$，共 $3$ 次。 不经过城市 $4$ 的路径只有路径 $3$，共 $2$ 次。

因此，依次输出 $2,3,2$。

样例解释 2

从城市 $1$ 到城市 $6$ 只有一种方式：城市 $1\to 2\to 5\to 6$，因此对于 $k=2,5$，不存在不经过城市 $k$ 的路径；对于 $k=3,4$，上述方式满足条件，传送器使用次数为 $3$。

因此，依次输出 $-1,3,3,-1$。

注意，由于传送器是单向的，虽然可以从城市 $3$ 到城市 $4$，但不能从城市 $4$ 到城市 $3$，因此不能通过城市 $1\to 4\to 3\to 6$ 这样的方式移动。

由 ChatGPT 4.1 翻译