import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; /* * Created on 2005/04/06 */ public class C_sekine { //つかエラー処理しなくてもいいよね? public static void main(String[] args) throws IOException { //input BufferedReader br = new BufferedReader(new FileReader("C1.txt")); //outputをファイルに書く BufferedWriter bw = new BufferedWriter(new FileWriter("C1_output.txt")); while (true) { //サイズ読む String line = br.readLine(); //0 0で終了 if (line.equals("0 0")) { break; } String strSize[] = line.split(" "); int width = Integer.parseInt(strSize[0]); int height = Integer.parseInt(strSize[1]); //テーブルをごっそり確保。いまなら番兵を無料でサービス。 String input[][] = new String[height + 1][width + 1];//charで良かった? for (int h = 0; h < height; h++) { line = br.readLine(); char characters[] = line.toCharArray(); for (int w = 0; w < width; w++) { input[h][w] = "" + characters[w]; } } //右端、下端は番兵。文字を入れとく for (int h = 0; h < height + 1; h++) { input[h][width] = "A"; } for (int w = 0; w < width + 1; w++) { input[height][w] = "A"; } //各マスから取れる最大シーケンスを格納するテーブル String output[][] = new String[height][width]; for (int h = 0; h < height; h++) { for (int w = 0; w < width; w++) { output[h][w] = input[h][w]; } } //動的計画法ちっくな手法で右下から String secretCode = "";//全体で最大のシーケンス for (int r = height - 1; 0 <= r; r--) { for (int c = width - 1; 0 <= c; c--) { //現在見てるマスが文字なら次 if (isNumber(input[r][c]) == false) continue; //そのマス数字なら右と下のマスも数字かどうかチェック //まず右のマス if (isNumber(input[r][c + 1])) { //下のマスも数字? if (isNumber(input[r + 1][c])) { //右と下、大きいほうを取ってoutputテーブルに格納 if (compareAsDecimal(output[r+1][c], output[r][c+1]) > 0) { output[r][c] = output[r][c] + output[r + 1][c]; } else { output[r][c] = output[r][c] + output[r][c + 1]; } } //右のマスだけ数字 else { output[r][c] = output[r][c] + output[r][c + 1]; } } //下のマスだけ数字 else if (isNumber(input[r + 1][c])) { output[r][c] = output[r][c] + output[r + 1][c]; } //最大シーケンスの更新 //数字を見つけたのがこれが最初の場合 if (secretCode.length() == 0) { secretCode = output[r][c]; } else if (compareAsDecimal(secretCode, output[r][c]) < 0) { secretCode = output[r][c]; } } } //最大シーケンス出力 String ans = trimZero(secretCode); System.out.println(ans); bw.write(ans); bw.newLine(); } br.close(); bw.close(); } public static boolean isNumber(String str) { if ("0123456789".indexOf(str) != -1) return true; else return false; } public static int compareAsDecimal(String str0, String str1) { //上位桁0削り str0 = trimZero(str0); str1 = trimZero(str1); //桁数によって場合わけ if (str0.length() < str1.length()) { return -1; } else if (str0.length() > str1.length()) { return 1; } else { return str0.compareTo(str1); } } public static String trimZero(String str) { while (str.length() > 0) { if (str.charAt(0) == '0') { str = str.substring(1); } else { break; } } return str; } }