分数: 450 点
问题陈述
我们有一个有向图 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} 是小写英文字母或 -.
If C_{i, j} 是小写英文字母,则从顶点正好有一条有向边 i 到顶点 j 标记 C_{i, j}。如果 C_{i, j} is -,顶点没有边 i 到顶点 j.
对于每个整数对 (i, j) 与 1 \leq i, j \leq N,回答以下问题:
- 在来自顶点的所有(不一定简单)路径中 i 到顶点 j 其边缘上的标签串联形成回文,这样的最短路径的长度是多少?如果没有这样的路径,答案是 -1.
约束
- 1 \leq N \leq 100
- N 是一个整数。
- 每个 C_{i, j} 是小写英文字母或
-.
输入
输入由标准输入按以下格式给出:
N
C_{1, 1}C_{1, 2}\ldotsC_{1, N}
C_{2, 1}C_{2, 2}\ldotsC_{2, N}
\vdots
C_{N, 1}C_{N, 2}\ldotsC_{N, N}
输出
让 A_{i, j} 是该对问题的答案 (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
4 ab-- --b- ---a c---
示例输出 1
0 1 2 4 -1 0 1 -1 3 -1 0 1 1 -1 -1 0
例如,考虑以下情况 (i, j) = (1, 4).
采取路径 1 \to 1 \to 2 \to 3 \to 4,并按顺序连接其边缘上的标签,我们得到字符串 abba,这是一个回文。
最多没有最长的路径 3 从顶点 1 到顶点 4 其标签串联是回文。因此,答案为 (1, 4) is 4.
请注意,空字符串也是回文。
示例输入 2
5 us--- -st-- --s-- u--s- ---ts
示例输出 2
0 1 3 -1 -1 -1 0 1 -1 -1 -1 -1 0 -1 -1 1 3 -1 0 -1 -1 -1 5 1 0