1126 The Secret Number

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1126

方針

ある位置までの可能な最大値でDPする。

ソース

#include<iostream>
#include<string>
using namespace std;

#define REP(i,a,b) for(int i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

char input[70][70];
string dp[70][70];

int comp(string s,string t) {
  if(s.length() != t.length()) return (s.length() - t.length());
  rep(i,s.length()) if(s[i] != t[i]) return (s[i] - t[i]);
  return 0;
}

int main() {
  int w,h,n;
  while(cin>>w>>h, w|h) {
    string s,above,left;
    rep(i,h) {
      cin>>s;
      rep(j,w) {
	dp[i][j] = "";
	input[i][j] = s[j];
      }
    }

    rep(i,h) rep(j,w) {
      char c = input[i][j];
      if(!(c <= '9' && c >= '0')) continue;
      above = ((i > 0 && dp[i-1][j] != "0") ? dp[i-1][j] : "") + string(1,c);
      left = ((j > 0 && dp[i][j-1] != "0") ? dp[i][j-1] : "") + string(1,c);
      dp[i][j] = (comp(above,left) <= 0) ? left : above;
    }

    string ans = "";
    rep(i,h) rep(j,w) if(comp(ans,dp[i][j]) < 0) ans = dp[i][j];
    cout<<ans<<endl;
  }
}