DP の計算順を工夫することで、もう少し高速に解くこともできます。

• \(\operatorname{DP} _ 0[i]\coloneqq\) 都市 \(1\) から都市 \(i\) まで行くときのテレポーター使用回数の最小値

を、（俗に配る DP と呼ばれる方法で） \(i\) について昇順で求めることを考えます。 \(\operatorname{DP} _ 1[i]\) を都市 \(i\) から都市 \(N\) まで行くときのテレポーター使用回数の最小値とします。

すると、\(i\) からの遷移を行う前に \(j\ (i\lt j\leq i+M)\) に到達可能であった場合、\(\big(\)その時点での \(\operatorname{DP} _ 0[j]\big)+\operatorname{DP} _ 1[j]\) の値は、都市 \(i,i+1,\ldots,j-1\) を通らずに都市 \(j\) を通って都市 \(1\) から都市 \(N\) まで行くときのテレポーター使用回数の最小値になります。
都市 \(k\) を使わない経路に対して、都市 \(k+1,k+2,\ldots,k+M-1\) のうち「使う都市であって番号最小のもの」について場合分けを行うことで、上の形式で得られる値のうちいずれかが求める最小値になっていることを示すことができます。

よって、さきに \(\operatorname{DP} _ 1\) をすべて計算しておくと、\(\operatorname{DP} _ 0\) の計算の際、遷移を行う前に答えを求めることができます。 時間計算量は \(O(NM)\) 時間となります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <string>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;
    vector<string> teleporter(N);
    for (auto &&S : teleporter)cin >> S;

    // x = min(x, y)
    const auto chmin{[](auto &&x, const auto &y) { if (x > y) x = y; }};

    // dp_1[i] := i から N まで最低何回のテレポートで到達できるか
    // dp_0[i] := 1 から i まで最低何回のテレポートで到達できるか
    // dp テーブルの要素はたかだか N - 1 なので、N を INF として用いてよい
    vector<unsigned> dp_1(N, N), dp_0(N, N);

    // dp_1[N] = 0 (1-indexed)
    // N から降順に dp テーブルを埋める
    dp_1.back() = 0;
    for (unsigned i = N; --i;)
        for (unsigned j = 0; j < M; ++j)
            if (teleporter[i][j] == '1')
                chmin(dp_1[i], dp_1[i + j + 1] + 1);

    // dp_0[1] = 0 (1-indexed)
    // 1 から昇順に dp テーブルを埋める
    dp_0.front() = 0;
    for (unsigned i = 0; i + 1 < N; ++i) {
        auto ans = N;
        for (unsigned j = 0; j < M; ++j) {
            // i からテレポートする遷移を計算する前に i + j へ到達可能
            // ⇔ i を通らずに i + j へ到達可能
            if (i + j + 1 < N && dp_0[i + j + 1] < N)
                chmin(ans, dp_1[i + j + 1] + dp_0[i + j + 1]);
            if (teleporter[i][j] == '1')
                chmin(dp_0[i + j + 1], dp_0[i] + 1);
        }
        if (i) {
            if (ans < N) cout << ans << " ";
            else cout << "-1 ";
        }
    }
    cout << endl;

    return 0;
}