ACM/ICPC 2003 国内予選

問題C :The Secret Number

PKU Problem 2030

動的計画法の問題。数字は右下のマスにのみ連結しているので、二次元配列の左上から順に走査していけばＯＫ。再帰処理で計算すると、タイムオーバーになります（多分ｗ）。

数字列はLong型の範囲（2^63-1）を超えてしまうので、String型で処理します。数字列の大小は桁数と辞書順で判断したんだけど、他に良い方法があるのかな？

• 新しい数字列の方が桁数が多い　→　採用
• 新旧の数字列の桁数が同じ　→　辞書順で比較

import java.io.*;
import java.util.*;

public class TheSecretNumber {

    public static void main(String[] args) {
        try {
//            Scanner in = new Scanner(System.in);
            Scanner in = new Scanner(new File("C.in"));
                    
            while (true) {
                int w = in.nextInt();
                int h = in.nextInt();
                
                // 終了条件
                if (w == 0 && h == 0)
                    break;
                
                // matrixの生成
                Square[][] mat = new Square[h][w];
                for (int dy = 0; dy < h; dy++) {
                    String line = in.next();
                    for (int dx = 0; dx < w; dx++) {
                        String digit = line.substring(dx,dx+1);        
                        mat[dy][dx] = new Square(digit,digit);
                    }
                }
                
                // 数字列はLong型の範囲を超えるので、String型で処理する
                String max = null;
                
                // matrixの探索
                // 数字列の比較は、文字数と辞書順で比較する
                for (int dy = 0; dy < h; dy++) {
                    for (int dx = 0; dx < w; dx++) {
                        // 当該のマスが数字じゃなかったら
                        if (!mat[dy][dx].num.matches("[0-9]"))
                            continue;
                                                
                        // 左側のマスのチェック
                        if (dx - 1 >= 0 && mat[dy][dx - 1].num.matches("[0-9]")) {
                            String newSeq = mat[dy][dx - 1].seq + mat[dy][dx].num;
                            if (mat[dy][dx].seq.length() < newSeq.length() || (mat[dy][dx].seq.length() == newSeq.length() && mat[dy][dx].seq.compareTo(newSeq) < 0))
                                mat[dy][dx].seq = newSeq;
                            
                            // 数字列の先頭が0の場合
                            if (mat[dy][dx].seq.startsWith("0"))
                                mat[dy][dx].seq = mat[dy][dx].seq.substring(1);
                        }
                        
                        // 上側のマスのチェック
                        if (dy - 1 >= 0 && mat[dy - 1][dx].num.matches("[0-9]")) {
                            String newSeq = mat[dy - 1][dx].seq + mat[dy][dx].num;
                            if (mat[dy][dx].seq.length() < newSeq.length() || (mat[dy][dx].seq.length() == newSeq.length() && mat[dy][dx].seq.compareTo(newSeq) < 0))
                                mat[dy][dx].seq = newSeq;
                            
                            // 数字列の先頭が0の場合
                            if (mat[dy][dx].seq.startsWith("0"))
                                mat[dy][dx].seq = mat[dy][dx].seq.substring(1);
                        }
                        
                        // 最大値の保存
                        if (max == null || (max.length() < mat[dy][dx].seq.length() || (max.length() == mat[dy][dx].seq.length() && max.compareTo(mat[dy][dx].seq) < 0)))
                            max = mat[dy][dx].seq;
                    }
                }
                
                System.out.println(max);
            
            }
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class Square {
    String num;
    String seq;
    
    // コンストラクタ
    Square(String num,String seq) {
        this.num = num;
        this.seq = seq;
    }
}