Figure 1. A Matrix
ACM International Collegiate Programming Contest
Japan Domestic, 2003-10-03
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.
数字('0'-'9')と英字('A'-'Z')が並んだ行列の中に隠された秘密の数を 見つけ出しなさい。行列のサンプルを図1に示します。
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 D2 ... Dn 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.
秘密の数は、秘密の数を隠すための惑わしの数といっしょに、行列の 中に十進表現で埋め込まれています。考慮する必要があるのは、 D1 D2 ... Dn という形の 数で、 Dk+1 (1 <= k < n) が行列の中で Dkのすぐ右隣または下隣にあるような数 です。そして、求める秘密の数はこのようにして埋め込まれた数のうち で最大のものです。
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 number in the matrix.
図1の行列の中には、908820、 23140037、 23900037、9930の4つの数が埋め込まれています。この ようすを図2に示します。この例からもわかるように、2つ以上の数 が部分的に数字列を共有している場合もあります。この例の場合は、 4つの数のうちで最大である23900037が、秘密の数ということになりま す。
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.
いっぽう、図3に示されているような列は数として正しくありません。 908A2には英字が含まれてしまっていますし、23149930では5番目の 数字が4番目の数字の上隣になっていますし、90037では3番目の数字が 2番目の数字の斜め右下になっています。
Write a program to figure out the secret number from a given matrix.
行列が与えられたとき、その中から秘密の数を取り出すプログラムを 書きなさい。
The input consists of multiple data sets, each data set representing a matrix. The format of each data set is as follows.
入力は複数のデータセットから成り、それぞれのデータセットが 1つの行列を表しています。1つのデータセットの形式は次のようになってい ます。
W H C11C12 ... C1W C21C22 ... C2W ... CH1CH2 ... CHW
In the first line of a data set, two positive integers W and H are given. W indicates the width (the number of columns) of the matrix, and H indicates the height (the number of rows) of the matrix. W+H is less than or equal to 70.
データセットの1行目には、2つの正の整数W とHが与えられています。 Wは行列の幅(カラムの数)であり、Hは行列の高さ (列の数)です。W+Hは70以下です。
H lines follow the first line, each of which corresponds to a row of the matrix in top to bottom order. The i-th row consists of W characters Ci1Ci2 ... CiW in left to right order. You may assume that each matrix includes at least one non-zero digit.
続くH行は、行列の各行を上から下に順に並べたものになって います。i番目の行は W文字から成り、これは Ci1Ci2 ... CiWが左から右に並んだものと なっています。すべての行列はすくなくとも1個、0でない数字を 含むものとします。
Following the last data set, two zeros in a line indicate the end of the input.
最後のデータセットの次には、1行に0が2つ書かれており、これで 入力の終わりを表しています。
For each data set, print the secret number (without leading zeros) on a line.
それぞれのデータセットに対し、秘密の数を(先頭に0をつけずに) 1行ずつ打ち出してください。
7 4 9R2A993 0E314A0 8A900DE 820R037 6 7 JH03HE ID7722 0DA1AH 30C9G5 99971A CA7EAI AHLBEM 20 2 A1234567891234CBDEGH BDEDF908034265091499 0 0
23900037 771971 12345908034265091499
Test your program against this first input data.
作成したプログラムに この1番目のデータ を処理させてください。
The ACM ICPC