The Secret Number

[問題] ACM/ICPC Japan Domestic 2003: Problem C

[解説]
Dynamic Programming
上から下、左から右、の順に各セルにおける最適な文字列を計算していけば、現在のセルの値を計算する時に、左のセルと上のセルがすでに最適解となっているので、それらの値の大きい方を選び、現在のセルに対応する文字をくっつけていきます。

[プログラム例]

// @author yutaka C++
#include<string>
#include<iostream>

#define MAX 72

using namespace std;

int row, column;
char M[MAX][MAX];
string T[MAX][MAX], secret;

string max( string str1, string str2 ){
    if ( str1.size() == str2.size() ){
        return ( str1 > str2 ) ? str1 : str2;
    } else {
        return ( str1.size() > str2.size() ) ? str1 : str2;
    }
}

void compute(){
    secret = "";
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            if ( isalpha( M[i][j] ) ) continue;
            
            T[i][j] = max( T[i-1][j], T[i][j-1] ) + M[i][j];
            // 最初の 0 を��辰9
            if ( T[i][j][0] == '0' ) T[i][j] = T[i][j].substr(1, T[i][j].size()-1);
            secret = max( secret, T[i][j] );
        }
    }
    
    cout << secret << endl;
}

bool input(){
    cin >> column >> row;
    if ( column == 0 && row == 0 ) return false;
    
    // 番弗踉;
    for ( int j = 0; j <= column; j++ ) { M[0][j] = 'A'; T[0][j] = "";}
    for ( int i = 0; i <= row; i++ ) { M[i][0] = 'A'; T[i][0] = "";}
    
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            cin >> M[i][j];
            T[i][j] = "";
        }
    }
    
    return true;
}

main(){
    while ( input() ) compute();
}