链接：https://ac.nowcoder.com/acm/problem/269368
来源：牛客网

题目描述                    

S 老师擅长 OI，他给你了这样一道签到题：

给定一个 n×m 的小写字母构成的字符矩阵 c，从左上角 (1,1) 走到右下角 (n,m)，只能向下或向右，求经过的格子形成的字符串字典序最小的方案。

你觉得很简单，决定立刻 AC。

输入描述:

第一行包含两个整数 n,m(1≤n,m≤210)，表示矩阵的行数和列数。

接下来的 n 行，第 $i$ 行包含长度为 m 的字符串，表示c(i,1),c(i,2),⋯ ,c(i,m)。

输出描述:

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

示例1

输入

2 3 

abc 

bza

输出

abca

说明

有 abca, abza 两种不同的路径，其中 abca 字典序最小。

====

第一想法就是用dfs来做，但是老是做的不对，应该是要回溯的，但是回溯还是不熟悉，然后看了别人的代码，应该是要bfs的，就是不懂为什么要2遍dfs，于是写了个dp的方法，结果超时了。。。dp是O(n)的时间复杂度，没想到也超时了。。先贴上dp的方法，再去研究下bfs的办法，得学习下。