分数: 500 点
问题陈述
有 N 城市编号城市 1, 城市 2, \ldots和城市 N.
还有单向传送器可以将你传送到不同的城市。
传送器是否可以直接从城市传送你 i (1\leq i\leq N) 到另一个由长度表示M 字符串 S_i 组成 0 和 1。 具体来说,对于 1\leq j\leq N,
- if 1\leq j-i\leq M 和 (j-i)- 第一个字符 S_i is
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. - If i+j>N,那么 j- 第一个字符 S_i is
0. - N 和 M 是整数。
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N
输出
打印 (N-2) 整数,以空格分隔,位于一行中。 的 i-th (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 无处可去。
因此,从城市出发有3条路径 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.