102915: [Atcoder]ABC291 F - Teleporter and Closed off

Problem Statement

There are $N$ cities numbered city $1$, city $2$, $\ldots$, and city $N$.
There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city $i$ $(1\leq i\leq N)$ to another is represented by a length-$M$ string $S_i$ consisting of 0 and 1. Specifically, for $1\leq j\leq N$,

• if $1\leq j-i\leq M$ and the $(j-i)$-th character of $S_i$ is 1, then a teleporter can send you directly from city $i$ to city $j$;
• otherwise, it cannot send you directly from city $i$ to city $j$.

Solve the following problem for $k=2,3,\ldots, N-1$:

Can you travel from city $1$ to city $N$ without visiting city $k$ by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print $-1$.

Constraints

• $3 \leq N \leq 10^5$
• $1\leq M\leq 10$
• $M<N$
• $S_i$ is a string of length $M$ consisting of 0 and 1.
• If $i+j>N$, then the $j$-th character of $S_i$ is 0.
• $N$ and $M$ are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $(N-2)$ integers, separated by spaces, in a single line. The $i$-th $(1\leq i\leq N-2)$ integer should be the answer to the problem for $k=i+1$.

Sample Input 1

5 2
11
01
11
10
00

Sample Output 1

2 3 2

A teleporter sends you

• from city $1$ to cities $2$ and $3$;
• from city $2$ to city $4$;
• from city $3$ to cities $4$ and $5$;
• from city $4$ to city $5$; and
• from city $5$ to nowhere.

Therefore, there are three paths to travel from city $1$ to city $5$:

• path $1$ : city $1$ $\to$ city $2$ $\to$ city $4$ $\to$ city $5$;
• path $2$ : city $1$ $\to$ city $3$ $\to$ city $4$ $\to$ city $5$; and
• path $3$ : city $1$ $\to$ city $3$ $\to$ city $5$.

Among these paths,

• two paths, path $2$ and path $3$, do not visit city $2$. Among them, path $3$ requires the minimum number of teleporter uses (twice).
• Path $1$ is the only path without city $3$. It requires using a teleporter three times.
• Path $3$ is the only path without city $4$. It requires using a teleporter twice.

Thus, $2$, $3$, and $2$, separated by spaces, should be printed.

Sample Input 2

6 3
101
001
101
000
100
000

Sample Output 2

-1 3 3 -1

The only path from city $1$ to city $6$ is city $1$ $\to$ city $2$ $\to$ city $5$ $\to$ city $6$.
For $k=2,5$, there is no way to travel from city $1$ to city $6$ without visiting city $k$.
For $k=3,4$, the path above satisfies the condition; it requires using a teleporter three times.

Thus, $-1$, $3$, $3$, and $-1$, separated by spaces, should be printed.

Note that a teleporter is one-way; a teleporter can send you from city $3$ to city $4$, but not from city $4$ to city $3$,
so the following path, for example, is invalid: city $1$ $\to$ city $4$ $\to$ city $3$ $\to$ city $6$.

问题描述

有编号为城市$1$，城市$2$，$\ldots$，城市$N$的$N$个城市。还有一个单向传送器可以将你传送到不同的城市。传送器能否直接将你从城市$i$$(1\leq i\leq N)$传送到另一个城市由一个长度为$M$的字符串$S_i$表示，该字符串由0和1组成。具体来说，对于$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$：

你能通过反复使用传送器从城市$1$到城市$N$不访问城市$k$吗？如果可以，打印你需要使用传送器的最小次数；否则，打印$-1$。

约束

• $3 \leq N \leq 10^5$
• $1\leq M\leq 10$
• $M<N$
• $S_i$是一个长度为$M$的字符串，由0和1组成。
• 如果$i+j>N$，那么$S_i$的第$j$个字符为0。
• $N$和$M$是整数。

输入

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

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

输出

在单行中打印$(N-2)$个用空格分隔的整数。第$i$个$(1\leq i\leq N-2)$整数应为对于$k=i+1$问题的答案。

样例输入1

5 2
11
01
11
10
00

样例输出1

2 3 2

传送器将你发送到

• 城市$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$和路径$3$，不访问城市$2$。其中路径$3$需要使用传送器的次数最少（两次）。
• 路径$1$是唯一没有城市$3$的路径。它需要使用传送器三次。
• 路径$3$是唯一没有城市$4$的路径。它需要使用传送器两次。

因此，用空格分隔的$2$，$3$和$2$应该被打印出来。

样例输入2

6 3
101
001
101
000
100
000

样例输出2

-1 3 3 -1

从城市$1$到城市$6$的唯一路径是城市$1$ $\to$ 城市$2$ $\to$ 城市$5$ $\to$ 城市$6$。
对于$k=2,5$，没有从城市$1$到城市$6$不访问城市$k$的方法。
对于$k=3,4$，上述路径满足条件；它需要使用传送器三次。

因此，用空格分隔的$-1$，$3$，$3$和$-1$应该被打印出来。

注意传送器是单向的； 传送器可以将你从城市$3$传送到城市$4$， 但不能从城市$4$传送到城市$3$，
因此，例如，以下路径是无效的： 城市$1$ $\to$ 城市$4$ $\to$ 城市$3$ $\to$ 城市$6$。