AT_abc394_e [ABC394E] Palindromic Shortest Path

[problemUrl]: https://atcoder.jp/contests/abc394/tasks/abc394_e 给定一个包含 $N$ 个顶点的有向图，顶点编号为 $1, 2, \ldots, N$。 边的信息由 $N^2$ 个字符 $C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N}$ 给出。其中 $C_{i, j}$ 为小写字母或 `-`。 - 当 $C_{i, j}$ 为小写字母时，存在一条从顶点 $i$ 到顶点 $j$ 的边，且该边的标签为 $C_{i, j}$。 - 当 $C_{i, j}$ 为 `-` 时，不存在从顶点 $i$ 到顶点 $j$ 的边。 对于所有满足 $1 \leq i, j \leq N$ 的整数对 $(i, j)$，请回答以下问题： - 找出从顶点 $i$ 到顶点 $j$ 的路径（不要求是简单路径），使得路径上边标签按顺序组成的字符串是回文。在所有满足条件的路径中，输出最短路径的长度。若不存在这样的路径，输出 $-1$。

输入通过标准输入按以下格式给出： > $N$ > $C_{1, 1}$ $C_{1, 2}$ $\ldots$ $C_{1, N}$ > $C_{2, 1}$ $C_{2, 2}$ $\ldots$ $C_{2, N}$ > $\vdots$ > $C_{N, 1}$ $C_{N, 2}$ $\ldots$ $C_{N, N}$

以整数对 $(i, j)$ 的答案 $A_{i, j}$ 按以下格式输出： > $A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, N}$ > $A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, N}$ > $\vdots$ > $A_{N, 1}$ $A_{N, 2}$ $\ldots$ $A_{N, N}$

### 约束条件 - $1 \leq N \leq 100$ - $N$ 为整数 - $C_{i, j}$ 为小写字母或 `-` ### 样例解释 1 以 $(i, j) = (1, 4)$ 为例：路径 $1 \to 1 \to 2 \to 3 \to 4$ 的边标签组成的字符串为 `abba`，这是一个回文。由于不存在长度小于 $4$ 的满足条件的路径，因此 $(i, j) = (1, 4)$ 的答案为 $4$。注意空字符串也被视为回文。 翻译由 DeepSeek R1 完成