Score : $500$ points

问题描述

有 $N$ 座城市，依次编号为城市 $1$、城市 $2$、$\ldots$ 和城市 $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$。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 12:09:18