/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の都市があり、都市 1, 都市 2, \ldots, 都市 N と番号づけられています。
いくつかの異なる都市の間は一方通行のテレポーターによって移動できます。
都市 i (1\leq i\leq N) からテレポーターによって直接移動できる都市は 0 と 1 からなる長さ M の文字列 S_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 を出力せよ。
制約
- 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 は整数
入力
入力は以下の形式で標準入力から与えられる。
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
の 3 つがあり、
- 都市 2 を通らない経路は経路 2, 経路 3 の 2つであり、そのうちテレポーターの使用回数が最小となるのは経路 3 で、この時 2 回使用する。
- 都市 3 を通らない経路は経路 1 のみであり、この時テレポーターは 3 回使用する。
- 都市 4 を通らない経路は経路 3 のみであり、この時テレポーターは 2 回使用する。
となります。よって、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 の場合には都市 k を通らずに都市 1 から都市 6 へ移動する方法は存在せず、
k=3,4 の場合には上の方法が条件をみたし、テレポーターを 3 回使用します。
よって、-1,3,3,-1 をこの順に空白区切りで出力します。
テレポーターは一方通行であるため、
都市 3 から都市 4 へはテレポーターによって移動できますが、
都市 4 から都市 3 へは移動できず、
都市 1 \to 都市 4 \to 都市 3 \to 都市 6
のような移動はできない事に注意してください。
Score : 500 points
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
0and1. - 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.