← 返回题目列表

AtCoder · past202005_f

F. 回文矩阵

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

分数: 7 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给定一个整数 N 和一个矩阵 a 尺寸 N×N 由小写英文字母组成。 你的任务是构造一个字符串 S 长度 N 满足以下条件:

  • 字符串 S 仅包含小写英文字母。
  • 字符串 S 是一个回文。回想一下,如果一个字符串在两个方向上的读取方式相同,则该字符串称为回文。
  • 每个字符 S_{i} 至少等于一个字符 a_{i,1},a_{i,2}, \ldots, a_{i,N}.

如果没有字符串可以满足上述所有条件,则必须指出这一事实。

约束

  • N 是一个整数。
  • 1 \leq N \leq 500
  • 每个字符 a_{i,j} 是一个小写英文字母。

输入

输入由标准输入按以下格式给出:

N 
a_{1,1}a_{1,2}\cdotsa_{1,N}
\vdots
a_{N,1}a_{N,2}\cdotsa_{N,N}

输出

如果存在字符串 S 满足所有条件,按以下格式打印答案:

S_{1}S_{2}S_{3}\cdotsS_{N}

如果存在多个满足所有条件的字符串,则可以打印其中任何一个。

如果没有解决方案,则打印 -1.


示例输入 1

2
yc
ys

示例输出 1

yy

示例输入 2

2
rv
jh

示例输出 2

-1