G. 字符矩阵

problem_type.remote_judge

1000ms

512MiB

The contest is ended. New submissions will be treated as correction submissions and will not be counted in the contest.

题目描述

给一个 $n\times m$ 的字符矩阵，有些位置有障碍（记为字符 #），需要在矩阵上找出一条起始点任意的路径（可以重复经过某个格子），使得字典序最大。

可以证明答案一定是有限的或者是由某个长度有限的字符串 $S$ 不断重复得到的。如果答案是有限的，直接输出之；如果答案是无限的，只需输出它的最短循环节。

第一行两个正整数 $n,m$ 。

后 $n$ 行，每行一个长度为 $m$ 的字符串，描述矩阵的第 $n$ 行。

一行一个字符串，表示答案。

3 3
###
#A#
###

3 4
####
#AB#
####

BA

3 4
####
#AA#
####

对于全部数据， $1\le n,m\le 10^3$ ，所有非障碍字符都是大写字母，矩阵至少有一个非障碍格。