公式解説の時間計算量は \(\Theta(N^3)\) ですが、時間計算量 \(\Theta(N^2)\) の解法が存在します。(ABC F～G 程度の難易度です)

動く方向を固定します。簡単のため、右方向への移動の場合を説明します。(他の方向でも同様です。)

開始位置の行を固定し、その行の数字を順に並べた文字列を \(S\) とすると、その行のマスから開始して得られる文字列は \(S\) を rotate したものです。よって、以下の問題に帰着します。

\(N\) 文字の文字列 \(S\) がある。\(S\) を rotate したもののうち辞書順で最大のものを求めよ。

\(S\) を \(2\) つ連結させた文字列を \(T\) とおくと、\(T\) の最初の \(N\) 個の suffix のうち辞書順で最大のものを求めればよいです。\(T\) の suffix array のうち \(N\) 未満の数で最も右に出現するものが rotate でずらす量となります。

C++ の実装例 https://atcoder.jp/contests/abc258/submissions/32939952

#include <bits/stdc++.h>
#include <atcoder/string>
using namespace std;
vector<int> dx = {1, 0, -1, 0, 1, 1, -1, -1};
vector<int> dy = {0, 1, 0, -1, 1, -1, 1, -1};
int main(){
  int N;
  cin >> N;
  vector<vector<char>> A(N, vector<char>(N));
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      cin >> A[i][j];
    }
  }
  string ans;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < 8; j++){
      int x = i, y = 0;
      if (j == 0 || j == 2){
        swap(x, y);
      }
      string S;
      for (int k = 0; k < N; k++){
        S += A[x][y];
        x += dx[j];
        y += dy[j];
        x = (x + N) % N;
        y = (y + N) % N;
      }
      string T = S + S;
      vector<int> sa = atcoder::suffix_array(T);
      int p = 0;
      for (int k = 0; k < N * 2; k++){
        if (sa[k] < N){
          p = sa[k];
        }
      }
      rotate(S.begin(), S.begin() + p, S.end());
      ans = max(ans, S);
    }
  }
  cout << ans << endl;
}