The Secret Number(PKU No.2030)

各要素がアルファベットか1桁の数字のH×W行列Mが与えられる。
任意の位置の数値要素(i,j)から(i+1,j)あるいは(i,j+1)の数値要素をたどっていってできる数値の内、最大の数値を求める。
制約
H+W<70

アルゴリズム

深さ優先だと $O(2^{W+H}) = O(2^{70})$ なのでむりぽ→DP
$DP_{i,j}$ をどこかから(i,j)までたどってできる最大の数値
$m_{i,j}$ を行列の(i,j)要素とする。ただし、要素が数値でない場合は-1と評価する。
$DP_{0,j} = DP_{i,0} = -1$ で初期化。
$1\leq i \leq H, 1\leq j \leq W$ について、
${ DP_{i,j} = \begin{cases} -1 & (m_{i,j} = -1) \\ m_{i,j} & (m_{i,j} \ne -1, m_{i-1,j}=m_{i,j-1}=-1) \\ m_{i,j} + 10\max\{ DP_{i-1,j}, DP_{i,j-1}\} & (otherwise) \end{cases} }$
答えは、 ${ \max\{ DP_{i,j}|0 < i\leq H, 0 < j \leq W \} }$

コード

先頭の0の処理とか比較とかめんどいので、BigIntegerを使った。
文字列でやるなら、0以外の数字から始まるようにして、比較を、まず桁数で比較→桁数が同じなら普通に(辞書順)比較すればいい。
また、はじめに $DP_{i,j} = m_{i,j}$ で初期化しておいた。

import java.util.*;
import java.math.*;
public class pku2030 {
	static Scanner stdin;
	final BigInteger B10 = new BigInteger("10");
	final BigInteger B0 = new BigInteger("0");
	final BigInteger Bn1 = new BigInteger("-1");
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new pku2030();
	}
	pku2030(){
		while(true){
			int W = stdin.nextInt(), H = stdin.nextInt();
			if( W==0 && H==0 ) break;
			System.out.println( solve(W, H) );
		}
	}
	/*m[i][j]は入力行列の(i,j)要素
	 *DP[0][j] = DP[i][0]= -1
	 *DP[i][j] = m[i][j] ((i,j)要素が数値でなければ-1) */
	BigInteger[][] init(int W, int H){
		BigInteger[][] DP = new BigInteger[H+1][W+1];
		for(int j=0; j<W+1; ++j){ DP[0][j] = new BigInteger("-1"); }
		for(int i=1; i<H+1; ++i){
			StringBuilder sb = new StringBuilder(" ");
			sb.append( stdin.next() );
			DP[i][0] = new BigInteger("-1");
			for(int j=1; j<W+1; ++j){
				Character ch = sb.charAt(j);
				if( Character.isDigit(ch) ) DP[i][j] = new BigInteger(ch.toString());
				else DP[i][j] = new BigInteger("-1");
			}
		}
		return DP;
	}
	BigInteger solve(int W, int H){
		BigInteger[][] DP = init(W,H);
		BigInteger ans = new BigInteger("0");
		for(int i=1; i<H+1; ++i){
			for(int j=1; j<W+1; ++j){
				//m[i][j] = -1 -> DP[i][j] = -1のまま
				if( DP[i][j].compareTo(Bn1) != 0 ){ //m[i][j]≠-1
					BigInteger max = DP[i-1][j];
					if(max.compareTo(DP[i][j-1]) < 0) max = DP[i][j-1];
					//m[i-1][j]=m[i][j-1]=-1 -> max = -1 -> DP[i][j] = m[i][j]のまま
					if(max.compareTo(B0) > 0) //otherwise DP[i][j] = 10*max(DP[i-1][j],DP[i][j-1]) + m[i][j]
						DP[i][j] = (max.multiply( B10 ).add( DP[i][j] ) );
					if( ans.compareTo( DP[i][j] ) < 0 ) ans = DP[i][j];
				}
			}
		}
		return ans;
	}
}