AOJ - Problem 1126 : The Secret Number

• 問題文

DPで解く問題です。ボードが数字であるとき、その数字の後ろに右か下の位置の数字をつなげることができます。dp[y][x]にボードの(x,y)の位置からつくることのできる最大の数字が入るように計算していきます。

右下からDPテーブルを埋めて行きましょう。(x,y)のボードが数字であったときdp[y+1][x]とdp[y][x+1]の大きい方を(x,y)の後ろにつなげることにします。dp[y+1][x]とdp[y][x+1]を比較するときは文字列の長さが大きい方が大きい数字とします。文字列の長さが等しいときは辞書順で大きい方が大きい数字とします。

'0'から始まる文字列で最大の長さのものを答えとして出力しないように気をつけましょう。

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;

int w,h;
string m[100];
string dp[100][100];

string max_string(const vector<string>& vs){
    int max_len=0;
    string s;
    for(int i=0 ; i < vs.size() ; i++ ){
        max_len = max( max_len , (int)vs[i].size() );
    }
    for(int i=0 ; i < vs.size() ; i++ ){
        if( vs[i].size() == max_len && ( s.empty() || s < vs[i] ) ){
            s = vs[i];
        }
    }
    return s;
}

void solve(){
    for(int y=0 ; y < 100 ; y++ ){
        for(int x=0 ; x < 100 ; x++ ){
            dp[y][x].clear();
        }
    }
    int max_len=0;
    string ans;
    for(int y=h-1 ; y >= 0 ; y-- ){
        for(int x=w-1 ; x >= 0 ; x-- ){
            if( isdigit( m[y][x] ) ){
                dp[y][x].push_back( m[y][x] );
                vector<string> vs;
                if( x != w-1 && isdigit( m[y][x+1] ) ){
                    vs.push_back( dp[y][x+1] );
                }
                if( y != h-1 && isdigit( m[y+1][x] ) ){
                    vs.push_back( dp[y+1][x] );
                }
		dp[y][x] += max_string( vs );
            }
            if( !dp[y][x].empty() && dp[y][x][0] != '0' ){
                max_len = max( max_len , (int)dp[y][x].size() );
            }
        }
    }
    for(int y=0 ; y < h ; y++ ){
        for(int x=0 ; x < w ; x++ ){
            if( dp[y][x].size() == max_len && ( ans.empty() || ans < dp[y][x] ) ){
                ans = dp[y][x];
            }
        }
    }
    cout << ans << endl;
}

int main(){
    while( cin >> w >> h , w || h ){
        for(int i=0 ; i < h ; i++ ){
            cin >> m[i];
        }
        solve();
    }
}