First of all, let us exclude the condition “without city \(k\)” and consider how to find the reachability and the minimum number of teleporter uses required.
By the conditions of the problem statement, for any cities \(i\) and \(j\) such that \(1\leq i<j\leq N\), one cannot travel from city \(j\) to city \(i\), so we don’t need a shortest-path algorithm algorithm on a general directed graph; all we need is Dynamic Programming (DP).

Specifically, we can find \(DP[i]=\) (the minimum number of teleporter uses required to travel from city \(1\) to city \(i\), or \(\infty\) if impossible) as follows. First of all, \(DP[1]=0\). Then, \(DP[i]\) can be found based on \(DP[1],DP[2],\ldots,DP[i-1]\) as:

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

This is because, for all path from city \(1\) to city \(i\), the city right before city \(i\) is one of cities \(i-1,i-2,\ldots,i-\min(M,i-1)\), and the minimum number of teleporters required to reach the last city plus one is the number to reach city \(i\); thus, their minimum.

This process finds (the minimum number of teleporter uses required to travel from city \(1\) to city \(i\)). Let \(DP_0[i]\) be this value. With a similar DP with opposite direction of moves, one can also find (the minimum number of teleporter uses required to travel from city \(i\) to city \(N\)). Let \(DP_1[i]\) be the value.

When it comes to a “path without city \(k\),” what kind of route do we need to consider? Here, a path from city \(1\) to city \(N\) without city \(k\) always contains a move that jumps over city \(k\), that is, a use of teleporter that directly sends from city \(i\) to city \(j\) such that \(1\leq i<k<j\leq N\). Thus, it is sufficient to consider all the paths city \(1\) \(\to\cdots\to\) city \(i\) \(\to\) city \(j\) \(\to\cdots\to\) city \(N\) for all pairs \((i, j)\) such that \(1\leq i<k<j\leq N\) and \(2\leq j-i\leq M\) to take into account all the paths that travels from city \(1\) to city \(N\) without city \(K\). Conversely, one cannot make a move that decreases the city number, so all of these paths satisfy the conditions.

When such a pair \((i,j)\) is fixed, the path city \(1\) \(\to\cdots\to\) city \(i\) \(\to\) city \(j\) \(\to\cdots\to\) city \(N\) requires at least:

• \(DP_0[i]\) uses during city \(1\) \(\to\cdots\to\) city \(i\)
• one use during city \(i\) \(\to\) city \(j\)
• \(DP_1[j]\) uses during city \(j\) \(\to\cdots\to\) city \(N\)

for a total of \((DP_0[i]+DP_1[j]+1)\) uses of teleporters at minimum; conversely, such a travel is possible.

Therefore, \(Ans[i]\), the minimum number of times you need to use a teleporter to travel from city \(1\) to city \(N\) without visiting city \(k\), can be written as

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

for each \(k\), there are \(\frac{M(M-1)}{2}\) pairs \((i,j)\) that satisfy the conditions. So, by precomputing \(DP_0[i]\) and \(DP_1[j]\), the answer can be found in an \(O(M^2)\) for each \(k\), for a total of \(O(NM^2)\) over all \(k\).

The precalculation of \(DP_0[i]\) and \(DP_1[j]\) costs \(O(NM)\) time, so the total time complexity is \(O(NM^2)\), which is fast enough to solve the problem.

Sample code in 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,k+m);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;
}

By the way, after computing one of \(DP_0[i]\) and \(DP_1[i]\), one can evaluate the other while also finding the answer, in order to solve this problem in a total of \(O(NM)\) time.