\(c\) を英小文字、\(S\) を回文とすると \(c, S, c\) をこの順に結合して得られる文字列は回文になります。逆に、長さ \(2\) 以上の文字列が回文である必要十分条件は最初の文字と最後の文字が等しく、最初および最後の文字を取り除いて得られる文字列が回文となることです。

以上の性質を利用することを考えると、この問題は（有向）グラフ上の最短経路問題として定式化できます。

\(G\) を \(N^2\) 頂点のグラフとして、頂点集合を \(\lbrace (1,1), (1,2), \ldots, (1, N), (2, 1), \ldots, (N, N) \rbrace\) とします。頂点 \((i, j)\) は問題で与えられるグラフにおける頂点 \(i\) から頂点 \(j\) へ向かうパスと対応させるように辺を定めることを考えます。

便宜上 \(G\) に始点 \(S\) を追加して \(N^2 + 1\) 頂点のグラフとして扱うと、以下のような辺を追加したグラフにおける \(S\) から \((i, j)\) への最短経路の長さが整数組 \((i, j)\) に対する本問題の答えとなります。

• 各 \(i\) について \(S\) から \((i, i)\) へ向かう重み \(0\) の辺
• \(C_{i, j} \neq\) - なる \((i, j)\) について \(S\) から \((i, j)\) へ向かう重み \(1\) の辺
• \(C_{k, i} \neq\) -, \(C_{j, l} \neq\) -, \(C_{k, i} = C_{j, l}\) を満たす \((i, j, k, l)\) について \((i, j)\) から \((k, l)\) へ向かう重み \(2\) の辺
  

\(1\) 種類目の辺は長さ \(0\) の回文、\(2\) 種類目の辺は長さ \(1\) の回文、\(3\) 種類目の辺は両端に同じ文字を追加することで回文の長さを \(2\) 増やすことに対応します。

\(G\) の頂点の数が \(O(N^2)\) であり、各頂点の次数は \(O(N^2)\) であるため \(G\) の辺の数は \(O(N^4)\) となり、BFS により \(O(N^4)\) 時間で答えを求めることができます。

辺に重みが付いていますが、重み \(0, 1\) の辺を先に処理することにより BFS により最短経路を求められることに注意してください。

実装例

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int inf = 1000000010;

int main() {
	int n;
	cin >> n;
	vector<vector<char>> c(n, vector<char>(n));
	rep(i, n) rep(j, n) cin >> c[i][j];
	vector<vector<int>> a(n, vector<int>(n, inf));
	queue<pair<int, int>> que;
	rep(i, n) {
		que.push({i, i});
		a[i][i] = 0;
	}
	rep(i, n) rep(j, n) {
		if (i == j or c[i][j] == '-') continue;
		que.push({i, j});
		a[i][j] = 1;
	}
	while (!que.empty()) {
		auto q = que.front(); que.pop();
		int i = q.first, j = q.second;
		rep(k, n) rep(l, n) {
			if (c[k][i] != '-' && c[j][l] != '-' && c[k][i] == c[j][l] && a[k][l] == inf) {
				a[k][l] = a[i][j] + 2;
				que.push({k, l});
			}
		}
	}
	rep(i, n) {
		rep(j, n) {
			cout << (a[i][j] == inf ? -1 : a[i][j]) << " \n"[j == n - 1];
		}
	}
}