← 返回题目列表

AtCoder · abc291_f

I. 传送器并关闭

中文机器翻译题面 查看原题

分数: 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.