/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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} は英小文字あるいは - です。
C_{i, j} が英小文字のとき頂点 i から頂点 j へ向かう辺がちょうど 1 つ存在してラベル C_{i, j} が付いており、C_{i, j} が - のとき頂点 i から頂点 j へ向かう辺は存在しません。
1 \leq i, j \leq N を満たす各整数組 (i, j) について、以下の問題に対する答えを求めてください。
- 頂点 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}
出力
整数組 (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
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 が得られます。これは回文であり、頂点 1 から頂点 4 へ向かう長さ 3 以下のパスであって辺に付けられたラベルの文字を順に結合した文字列が回文となるものは存在しないため (i, j) = (1, 4) に対する答えは 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
Score : 450 points
Problem Statement
We have a directed graph with N vertices, numbered 1, 2, \ldots, N.
Information about the edges is given by N^2 characters C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N}. Here, each C_{i, j} is either a lowercase English letter or -.
If C_{i, j} is a lowercase English letter, then there is exactly one directed edge from vertex i to vertex j labeled C_{i, j}. If C_{i, j} is -, there is no edge from vertex i to vertex j.
For each integer pair (i, j) with 1 \leq i, j \leq N, answer the following question:
- Among all (not necessarily simple) paths from vertex i to vertex j whose concatenation of labels on the edges forms a palindrome, what is the length of the shortest such path? If there is no such path, the answer is -1.
Constraints
- 1 \leq N \leq 100
- N is an integer.
- Each C_{i, j} is either a lowercase English letter or
-.
Input
The input is given from Standard Input in the following format:
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}
Output
Let A_{i, j} be the answer to the question for the pair (i, j). Print them in the following format:
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}
Sample Input 1
4 ab-- --b- ---a c---
Sample Output 1
0 1 2 4 -1 0 1 -1 3 -1 0 1 1 -1 -1 0
For example, consider the case (i, j) = (1, 4).
By taking the path 1 \to 1 \to 2 \to 3 \to 4, and concatenating the labels on its edges in order, we get the string abba, which is a palindrome.
There is no path of length at most 3 from vertex 1 to vertex 4 whose concatenation of labels is a palindrome. Thus, the answer for (1, 4) is 4.
Note that the empty string is also a palindrome.
Sample Input 2
5 us--- -st-- --s-- u--s- ---ts
Sample Output 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