1126-The Secret Number
問題概要
WxHの数値や文字のかかれたマス目が与えられる。
このマス目を下または右に移動して作り出せる数のうち最大の物を求めよ
考え方
最大70文字の長さになるのでlong longでもオーバーフローするので文字列を用いる。
後は座標(x,y)から作り出せる最大の数値をメモ化して答えを求める。
実装(C++)
#include <iostream> #include <cstring> using namespace std; string *MAP; int H,W; string res; int dx[2]={0,1},dy[2]={1,0}; bool comp(string a,string b){ if(a.size()>b.size())return true; if(a.size()<b.size())return false; if(a>b)return true; return false; } string dp[100][100]; string dfs(int x,int y,string val){ if(!dp[x][y].empty())return dp[x][y]; string res="",t; for(int k=0;k<2;k++){ if(x+dx[k]>=W||y+dy[k]>=H)continue; if(MAP[x+dx[k]][y+dy[k]]>='0'&&MAP[x+dx[k]][y+dy[k]]<='9'){ t=dfs(x+dx[k],y+dy[k],val+MAP[x+dx[k]][y+dy[k]]); if(comp(t,res))res=t; } } return dp[x][y]=MAP[x][y]+res; } int main(){ for(;cin>>H>>W,W;){ MAP=new string[W]; for(int i=0;i<W;i++) cin>>MAP[i]; res=""; string t; for(int i=0;i<W;i++) for(int j=0;j<H;j++) dp[i][j]=""; for(int i=0;i<W;i++){ for(int j=0;j<H;j++){ if(MAP[i][j]>='1'&&MAP[i][j]<='9'){ t=dfs(i,j,MAP[i].substr(j,1)); if(comp(t,res))res=t; } } } cout<<res<<endl; } return 0; }