#P2030. The Secret Number
The Secret Number
描述
你的任务是从一个矩阵中找出隐藏的秘密数字,该矩阵的每个元素是一个数字(-)或字母(-)。图1展示了一个示例矩阵。
图1:矩阵
秘密数字和其他非秘密数字以十进制数字序列的形式编码在矩阵中。你只需要考虑满足以下条件的数字序列 :()在矩阵中必须位于 的正右侧或正下方。你需要找到以这种方式编码的最大数字。
在图1的矩阵中,图2展示了四个编码数字:、、 和 。可以看到,通常两个或多个编码数字可能共享一个公共子序列。在这种情况下,秘密数字是 ,因为它是矩阵中所有编码数字中最大的。
图2:编码数字
相反,图3展示的序列应被排除: 包含字母; 的第五位数字位于第四位的上方; 的第三位数字位于第二位的右下方。
图3:无效序列
编写一个程序,从给定的矩阵中找出秘密数字。
输入
输入包含多个数据集,每个数据集表示一个矩阵。每个数据集的格式如下:
在数据集的第一行,给出两个正整数 和 。 表示矩阵的宽度(列数), 表示矩阵的高度(行数)。 不超过 。
接下来的 行对应于矩阵的行(从上到下顺序)。第 行包含 个字符 (从左到右顺序)。你可以假设矩阵中至少包含一个非零数字。
在最后一个数据集之后,一行中的两个 表示输入结束。
输出
对于每个数据集,输出秘密数字。前导零应被省略。
样例输入
7 4
9R2A993
0E314A0
8A900DE
820R037
6 7
JH03HE
ID7722
0DA1AH
30C9G5
99971A
CA7EAI
AHLBEM
20 2
A1234567891234CBDEGH
BDEDF908034265091499
0 0
样例输出
23900037
771971
12345908034265091499