← 返回题目列表

AtCoder · abc394_e

H. 回文最短路径

中文机器翻译题面 查看原题

分数: 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