AOJ 1126 : The Secret Number

問題リンク：The Secret Number | Aizu Online Judge

問題概要：
略

使用した言語：C++

解法；
左と上をみて値の大きいほうを保存していく
ただし普通に比較するのではなく、リーディング０も考慮しなければならない

cmp2は作ったけどいらなかったっぽい

コード：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<sstream>
#include<cstring>
#include<vector>
using namespace std;

bool cmp1(const string& a,const string& b)
{
  int size_a,size_b;
  int start_a,start_b;
  start_a = start_b = 0;
  size_a = a.size(),size_b = b.size();
  if(a[0] == '0')
    for(int i=0;i<a.size() && a[i] == '0';i++)
      size_a--,start_a++;

  if(b[0] == '0')
    for(int i=0;i<b.size() && b[i] == '0';i++)
      size_b--,start_b++;

  if(size_a != size_b)
    return size_a < size_b;

  for(int i=0;i<size_a;i++)
    {
      if(a[start_a+i] != b[start_b+i])
	return a[start_a+i] < b[start_b+i];
    }
  return true;
}

bool cmp2(const string& a,const string& b)
{
  if(a.size() != b.size())
    return a.size() < b.size();
  for(int i=0;i<a.size();i++)
    {
      if(a[i] != b[i])
	return a[i] < b[i];
    }
  return true;
}

int main()
{

  int W,H;
  while(cin >> W >> H,W|H)
    {
     
      vector<vector<string> > G;
      G.resize(H);
      for(int i=0;i<H;i++)
	{
	  G[i].resize(W);
	  string line;
	  cin >> line;

	  for(int j=0;j<W;j++)
	    {
	      G[i][j] = line[j];
	    }
	}

      string G2[H][W];
      string ans = "";
      for(int i=0;i<H;i++)
	{
	  for(int j=0;j<W;j++)
	    {
	      if(isalpha(G[i][j][0]))
		continue;
	    
	      G2[i][j] = max(G2[i][j],G[i][j],cmp1);
	      string A,B;
	      A = B = G2[i][j];
	      if(j-1 >= 0 && !isalpha(G[i][j-1][0]))
		A = max(G2[i][j],G2[i][j-1]+G2[i][j],cmp1);

	      if(i-1 >= 0 && !isalpha(G[i-1][j][0]))
		B = max(G2[i][j],G2[i-1][j]+G2[i][j],cmp1);
	      G2[i][j] = max(A,B,cmp1);
	      ans = max(G2[i][j],ans,cmp1);
	    
	    }
	}
    
      
      for(int i=0;i<ans.size()&&ans[i] == '0';i++)
	ans[i] = ' ';
      stringstream ss;
      ss << ans;
      ss >> ans;
      
     cout << ans << endl;

      }
    
  return 0;
}