链接: https://cses.fi/problemset/task/3359

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你得到一个 $n \times n$ 的网格，每个格子里有一个字母。

你需要从左上角格子移动到右下角格子。你只能向右或向下移动。

你能构造出的字典序最小的字符串是什么？

输入

第一行包含一个整数 $n$：网格的大小。

之后有 $n$ 行描述网格。每行包含 $n$ 个介于 A 和 Z 之间的字母。

输出

输出字典序最小的字符串。

数据范围

$1 \le n \le 3000$

样例输入

4
AACA
BABC
ABDA
AACA

样例输出

AAABACA