Minimal Grid Path

题目描述

给定一个大小为 $n \times n$ 的网格，每个格子里都包含一个字母。 你应当从左上角的格子移动到右下角的格子。你只能向右或向下移动。 你能构造出的字典序（按字典顺序）最小的字符串是什么？

输入格式

第一行是一个整数 $n$：网格的大小。 接下来有 $n$ 行表示网格。每一行包含 $n$ 个字母，字母在 A 到 Z 之间。

输出格式

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

4
AACA
BABC
ABDA
AACA

AAABACA

提示

$1 \le n \le 3000$

标签: CSES3359|动态规划|DP

来源

CSES3359|动态规划|DP