AOJ1126 The Secret Number

問題リンク The Secret Number

• 概要

W*Hのボードに、数字もしくはアルファベットが書いてある。あるマスの数字はその下、もしくは右にある数字と繋げて読むことができる。このとき、ボードの中で最も数が大きくなる数字の列を答えよ。
W+H <= 70

• 解法

DPです。マス(i, j)の数字を先頭とする最大の数列は(i+1, j)と(i, j+1)を使って求めることができるので、ボードの右下からDP表を埋めることができます。
dp[i][j] = max(a+dp[i+1][j], a+dp[i][j+1])
ただし、注意があります。ここでいう大きいとは、
文字数が長い方が大きい。文字数が等しかったら、数字として大きい方が大きい。とします。
なぜなら、数字として大きいかだけを見てしまったら、"0001"と"999"の場合"999"が採用されてしまいます。これの何がまずいかというと、あるマスが今の結果を使って整数を作るとき、"?999"よりも"?0001"の方が数値として大きくなるので、"999"を採用してしまうと答えが求まらないのです。(自分はこれで結構はまりました）
数値の比較にBigIntegerを使っていますが、数値の大きい方は文字列として、辞書的に大きい方になるので、StringのcompareTo()でも大丈夫なんじゃないかと思います。

• ソース

import java.math.BigInteger;
import java.util.Scanner;

//The Secret Number
public class AOJ1126 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int w = sc.nextInt();
			int h = sc.nextInt();
			if((w|h)==0)break;
			char[][] m = new char[h][w];
			for(int i=0;i<h;i++)m[i]=sc.next().toCharArray();
			String[][] dp = new String[h][w];
			String res = "0";
			for(int i=h-1;i>=0;i--)for(int j=w-1;j>=0;j--){
				if(Character.isUpperCase(m[i][j]))continue;
				String l = m[i][j]+"";
				String d = m[i][j]+"";
				if(i+1<h&&!Character.isUpperCase(m[i+1][j]))d+=dp[i+1][j];
				if(j+1<w&&!Character.isUpperCase(m[i][j+1]))l+=dp[i][j+1];
				if(l.length()!=d.length()){
					dp[i][j] = l.length()>d.length()?l:d;
				}
				else{
					BigInteger bl = new BigInteger(l);
					BigInteger bd = new BigInteger(d);
					if(bl.compareTo(bd)>0)dp[i][j] = l;
					else dp[i][j] = d;
				}
				BigInteger b = new BigInteger(dp[i][j]);
				if(b.compareTo(new BigInteger(res))>0){
					res = dp[i][j];
				}
			}
			System.out.println(new BigInteger(res).toString());
		}
	}

	public static void main(String[] args) {
		new AOJ1126().run();
	}
}