Your job is to find out the secret number hidden in a matrix, each of whose element is a digit ('0'-'9') or a letter ('A'-'Z'). You can see an example matrix in Figure 1.
Figure 1: A Matrix
The secret number and other non-secret ones are coded in a matrix as sequences of digits in a decimal format. You should only consider sequences of digits D1
such that Dk+1
(1 <= k < n) is either right next to or immediately below Dk
in the matrix. The secret you are seeking is the largest number coded in this manner.
Four coded numbers in the matrix in Figure 1, i.e., 908820, 23140037, 23900037, and 9930, are depicted in Figure 2. As you may see, in general, two or more coded numbers may share a common subsequence. In this case, the secret number is 23900037, which is the largest among the set of all coded numbers in the matrix.
Figure 2: Coded Numbers
In contrast, the sequences illustrated in Figure 3 should be excluded: 908A2 includes a letter; the fifth digit of 23149930 is above the fourth; the third digit of 90037 is below right of the second.
Figure 3: Inappropriate Sequences
Write a program to figure out the secret number from a given matrix.