頂点や行・列の番号を0-indexedで考えることにします。
\(x_{i,j}\) の値は \(a_{(i \bmod N), (j \bmod N)}\) に一致するため、\(a_{i,j}=1\) の時、任意の \(u \bmod N = i\) であるような頂点 \(u\) から任意の \(v \bmod N = j\) であるような頂点 \(v\) への有向辺が存在します。このため、有向辺を使った移動を \(1\) 回行った時点で頂点番号は \(\mathrm{mod}\ N\) で考えれば十分であり、基本的には \(A\) を隣接行列とする有向グラフ上の最短経路長を求めれば良いです。
ただし、本問では \(s_i \bmod N = t_i \bmod N\) の場合に少し問題が発生します。\(A\) を隣接行列とする有向グラフ上の最短経路長は \(0\) となりますが、これは有向辺を \(1\) 回以上使うという前提に反した移動を考えているので不適です。
有向辺を \(1\) 回以上使った場合の最短経路長は、以下のようにBFSやワーシャルフロイド法を少し修正することで求められます。

• \(a_{i,j}=1\) なる \((i,j)\) に対して \(i\) から \(j\) への距離が \(1\) という初期状態から始めてBFSやワーシャルフロイド法を使う( \(i = j\) ならば \(i\) から \(j\) への距離は \(0\) という初期化は行わない)。
• 各頂点に対して辺を \(1\) 回以上使ったかどうかの情報を持つ \(2N\) 頂点の有向グラフでBFSやワーシャルフロイド法を使う。