まず、「都市\(k\)を通らず」という条件を抜いて、移動できるかの判定およびテレポーターの使用回数の最小値を求めることを考えます。
これは、問題の条件から、\(1\leq i<j\leq N\) であるような都市 \(i,j\) について、都市 \(j\) から都市 \(i\) への移動(都市の番号が減少するような方向への移動) ができない事から、一般の有向グラフ上での最短経路アルゴリズムを用いずとも, 動的計画法によって求めることができます。

具体的には、\(DP[i]=\)(都市 \(1\) から都市 \(i\) へ移動するために必要なテレポーターの使用回数の最小値, 到達不能な場合は \(\infty\) ) を次のようにして求める事ができます。まず、\(DP[1]=0\) です。 そして、\(DP[i]\) は \(DP[1],DP[2],\ldots,DP[i-1]\)の結果を元に、

\[ DP[i]=\displaystyle\min_{1\leq j\leq \min(M,i-1)} \left( DP[i-j]+ \begin{cases} 1 & (S[i-j][j]= \text{‘1’} のとき) \\ \infty & (S[i-j][j]= \text{‘0’} のとき) \end{cases} \right) \]

として計算する事ができます。これは、都市 \(1\) から都市 \(i\) へ移動する任意の経路において、都市 \(i\) に移動する直前にいる都市は都市 \(i-1,i-2,\ldots,i-\min(M,i-1)\) のいずれかであり、直前の都市に到達するまでの使用回数に\(1\) を加えたものが都市 \(i\) へ移動するために使用した回数になるため、それらの最小値を求めれば良いからです。

この過程で、「都市 \(1\) から都市 \(i\) へ移動するために必要なテレポーターの使用回数の最小値」を求める事ができます。以下、これを \(DP_0[i]\) とします。 移動方向の向きを逆にして同様のDPを行う事で、「都市 \(i\) から都市 \(N\) へ移動するために必要なテレポーターの使用回数の最小値」も求める事ができます。以下、これを \(DP_1[i]\) とします。

さて、「都市\(k\)を通らず」という条件を付加した時、どういった経路について考慮する必要があるかについて考えます。ここで、都市\(k\) を通らず、都市 \(1\) から都市 \(N\) へ移動する経路においては必ず都市 \(k\) を飛び越す移動、すなわち、\(1\leq i<k<j\leq N\) であって、テレポーターによって都市 \(i\) から都市 \(j\) へ直接移動するような部分が必ず含まれます。よって、\(1\leq i<k<j\leq N\), \(2\leq j-i\leq M\) であるような組 \((i,j)\) について、都市 \(1\) \(\to\cdots\to\) 都市 \(i\) \(\to\) 都市 \(j\) \(\to\cdots\to\) 都市 \(N\) と行った経路をすべて考えれば「都市 \(k\) を通らずに都市 \(1\) から都市 \(N\) へ移動する経路」を全て含んでいます。逆に、都市の番号が減少するような方向への移動ができない事から、このような経路は全て条件をみたしています。

このような組 \((i,j)\) を固定した時の都市 \(1\) \(\to\cdots\to\) 都市 \(i\) \(\to\) 都市 \(j\) \(\to\cdots\to\) 都市 \(N\) と移動するために必要なテレポーターの使用回数の最小値は、最低でも

• 都市 \(1\) \(\to\cdots\to\) 都市 \(i\) で \(DP_0[i]\) 回
• 都市 \(i\) \(\to\) 都市 \(j\) で \(1\) 回
• 都市 \(j\) \(\to\cdots\to\) 都市 \(N\) で\(DP_1[j]\) 回

で \(DP_0[i]+DP_1[j]+1\) 回必要であり、逆にこの回数で移動する事は可能です。

以上の事から、都市 \(k\) を通らずに都市 \(1\) から都市 \(N\) へ移動する時のテレポーターの使用回数の最小値を \(Ans[i]\) とすると、 \(Ans[i]\) は、

\[ \displaystyle\min_{\substack{1\leq i<k<j\leq N\\ 2\leq j-i\leq M}} DP_0[i]+DP_1[j]+1 \]

と書け、各 \(k\) について条件をみたす \((i,j)\) の組の数は 高々 \(\frac{M(M-1)}{2}\) 個である事から、事前に \(DP_0[i]\), \(DP_1[j]\) を計算しておけば、各 \(k\) に対して \(O(M^2)\) で答えを求める事ができ、全ての \(k\) について合わせて \(O(NM^2)\) で求める事ができます。

\(DP_0[i]\), \(DP_1[j]\) の事前計算には \(O(NM)\) だけかかる事から、全体でも時間計算量は \(O(NM^2)\) であり、十分高速にこの問題を解く事ができました。

c++ による実装例 :

#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e+9

int main(void) {
	int n,m,ans;
	cin>>n>>m;
	vector<string> s(n);
	for(int i=0;i<n;i++)cin>>s[i];

	vector<int> dp0(n,INF),dp1(n,INF);
	dp0[0]=0;
	for(int i=1;i<n;i++){
		for(int j=1;j<=min(m,i);j++){
			if(s[i-j][j-1]=='1')dp0[i]=min(dp0[i],dp0[i-j]+1);
		}
	}
	dp1[n-1]=0;
	for(int i=n-2;i>=0;i--){
		for(int j=1;j<=min(m,n-1-i);j++){
			if(s[i][j-1]=='1')dp1[i]=min(dp1[i],dp1[i+j]+1);
		}
	}
  
	for(int k=1;k<n-1;k++){
                ans=INF;
		for(int i=max(k-m+1,0);i<k;i++){
			for(int j=k+1;j<min(n,i+m+1);j++){
				if(s[i][j-i-1]=='1')ans=min(ans,dp0[i]+dp1[j]+1);
			}
		}
                if(ans==INF)cout<<-1;
		else cout<<ans;
		if(k<(n-2))cout<<" ";
		else cout<<endl;
	}	
	return 0;
}

なお、\(DP_0[i],DP_1[j]\) の一方の計算の後に、もう一方の計算を行う際にまとめて答えについても計算していくことで \(O(NM)\) でこの問題を解く事もできます。