Let us use 0-indexed labels for the vertices, rows, and columns.
The value \(x_{i,j}\) equals \(a_{(i \bmod N), (j \bmod N)}\), so if \(a_{i,j}=1\), there is a directed edge from any vertex \(u\) such that \(u \bmod N = i\) to any vertex \(v\) such that \(v \bmod N = j\). Therefore, after traversing one directed edge, we may consider the vertex labels modulo \(N\), and the answer is basically the shortest path length on the graph whose adjacency matrix is \(A\).
However, the situation is a bit tricky when \(s_i \bmod N = t_i \bmod N\). In this case, the shortest path length on the graph whose adjacency matrix is \(A\) is \(0\), but this is invalid because it violates the premise that at least one directed edge is used.
To find the shortest length of a path that uses at least one directed edge, slightly modify BFS or the Floyd-Warshall algorithm as follows.

• Start with the initial state where the distance from \(i\) to \(j\) is \(1\) for \((i,j)\) such that \(a_{i,j}=1\). (Do not set it to \(0\) even if \(i = j\).)
• Alternatively, use a directed graph with \(2N\) vertices to track whether at least one edge has been used for each vertex.