#include<bits/stdc++.h>
using namespace std;
string a[ 1000 ] [ 1000 ] ; //-- represent the input grid
string f[ 1000 ] [ 1000 ] ; //-- represent the array used for memoization
bool calculated[ 1000 ] [ 1000 ] ; //-- false if we have not calculate the value before, and true if we have
int n,m;
//-- sort the string str and return it
string srt( string & str) {
sort( str.begin ( ) , str.end ( ) ) ;
return str;
}
//-- return the smallest of x and y
string smallest( string & x, string & y) {
for ( int i = 0 ; i < x.size ( ) ; i++ ) {
if ( x[ i] < y[ i] ) return x;
if ( x[ i] > y[ i] ) return y;
}
return x;
}
string solve( int i, int j,int n,int m) {
if ( i == 1 && j == 1 ) return a[ i] [ j] ; //-- if we have reached the buttom right cell (I assumed the array is 1-indexed
if ( calculated[ i] [ j] ) return f[ i] [ j] ; //-- if we have calculated this before
string ans;
if ( i == n)
{
string rtt= a[ i] [ j] + solve( i, j + 1 ) ;
ans = srt( rtt) ;
} //-- if we are at the buttom boundary
else if ( j == m)
{
string rtt= a[ i] [ j] + solve( i + 1 , j) ;
ans = srt( rtt) ;
}
//-- if we are at the right boundary
else
{
string s11= solve( i, j + 1 ) ;
string s22= solve( i + 1 , j) ;
string rtt= a[ i] [ j] + smallest( s11,s22 ) ;
ans = srt( rtt) ;
}
calculated[ i] [ j] = true ; //-- to fetch the calculated result in future calls
f[ i] [ j] = ans;
return ans;
}
int main( )
{
int n,m;
cin >> n>> m;
for ( int i= 0 ; i< n; i++ )
for ( int j= 0 ; j< m; j++ )
cin >> a[ i] [ j] ;
cout << solve( n,m,n,m) ;
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKc3RyaW5nIGFbMTAwMF1bMTAwMF07ICAgICAgICAgICAgIC8vLS0gcmVwcmVzZW50IHRoZSBpbnB1dCBncmlkCnN0cmluZyBmWzEwMDBdWzEwMDBdOyAgICAgICAgICAgICAvLy0tIHJlcHJlc2VudCB0aGUgYXJyYXkgdXNlZCBmb3IgbWVtb2l6YXRpb24KYm9vbCBjYWxjdWxhdGVkWzEwMDBdWzEwMDBdOyAgICAgIC8vLS0gZmFsc2UgaWYgd2UgaGF2ZSBub3QgY2FsY3VsYXRlIHRoZSB2YWx1ZSBiZWZvcmUsIGFuZCB0cnVlIGlmIHdlIGhhdmUKaW50IG4sbTsKCi8vLS0gc29ydCB0aGUgc3RyaW5nIHN0ciBhbmQgcmV0dXJuIGl0CnN0cmluZyBzcnQoc3RyaW5nICZzdHIpewogICAgc29ydChzdHIuYmVnaW4oKSwgc3RyLmVuZCgpKTsKICAgIHJldHVybiBzdHI7Cn0KCgovLy0tIHJldHVybiB0aGUgc21hbGxlc3Qgb2YgeCBhbmQgeQpzdHJpbmcgc21hbGxlc3Qoc3RyaW5nICYgeCwgc3RyaW5nICZ5KXsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgeC5zaXplKCk7IGkrKyl7CiAgICAgICAgaWYgKHhbaV0gPCB5W2ldKSByZXR1cm4geDsKICAgICAgICBpZiAoeFtpXSA+IHlbaV0pIHJldHVybiB5OwogICAgfQogICAgcmV0dXJuIHg7Cn0KCgpzdHJpbmcgc29sdmUoaW50IGksIGludCBqLGludCBuLGludCBtKXsKICAgIGlmIChpID09IDEgJiYgaiA9PSAxKSByZXR1cm4gYVtpXVtqXTsgICAgICAgLy8tLSBpZiB3ZSBoYXZlIHJlYWNoZWQgdGhlIGJ1dHRvbSByaWdodCBjZWxsIChJIGFzc3VtZWQgdGhlIGFycmF5IGlzIDEtaW5kZXhlZAogICAgaWYgKGNhbGN1bGF0ZWRbaV1bal0pIHJldHVybiBmW2ldW2pdOyAgICAgICAvLy0tIGlmIHdlIGhhdmUgY2FsY3VsYXRlZCB0aGlzIGJlZm9yZSAKICAgIHN0cmluZyBhbnM7CiAgICBpZiAoaSA9PSBuKSAKICAgIHsKICAgIAlzdHJpbmcgcnR0PWFbaV1bal0gKyBzb2x2ZShpLCBqICsgMSk7CiAgICBhbnMgPSBzcnQocnR0KTsgCiAgICB9Ly8tLSBpZiB3ZSBhcmUgYXQgdGhlIGJ1dHRvbSBib3VuZGFyeQogICAgZWxzZSBpZiAoaiA9PSBtKSAKICAgIHsKICAgIAlzdHJpbmcgcnR0PWFbaV1bal0gKyBzb2x2ZShpICsgMSwgaik7CiAgICBhbnMgPSBzcnQocnR0KTsgCiAgICB9CiAgICAgLy8tLSBpZiB3ZSBhcmUgYXQgdGhlIHJpZ2h0IGJvdW5kYXJ5CiAgICBlbHNlIAogICAgewogICAgCXN0cmluZyBzMTE9c29sdmUoaSwgaiArIDEpOwogICAgCXN0cmluZyBzMjI9c29sdmUoaSArIDEsIGopOwogICAgCXN0cmluZyBydHQ9YVtpXVtqXSArIHNtYWxsZXN0KHMxMSxzMjIgKTsKICAgIGFucyA9IHNydChydHQpOyAKICAgIH0KICAgIGNhbGN1bGF0ZWRbaV1bal0gPSB0cnVlOyAgICAgICAgLy8tLSB0byBmZXRjaCB0aGUgY2FsY3VsYXRlZCByZXN1bHQgaW4gZnV0dXJlIGNhbGxzCiAgICBmW2ldW2pdID0gYW5zOwogICAgcmV0dXJuIGFuczsKfQoKCgppbnQgbWFpbigpCnsKaW50IG4sbTsKICAgIGNpbj4+bj4+bTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICBmb3IoaW50IGo9MDtqPG07aisrKQogICAgY2luPj5hW2ldW2pdOwogICAgCiAgICBjb3V0PDxzb2x2ZShuLG0sbixtKTsKICAgIHJldHVybiAwOwp9
compilation info
prog.cpp: In function 'std::string solve(int, int, int, int)':
prog.cpp:31:41: error: too few arguments to function 'std::string solve(int, int, int, int)'
string rtt=a[i][j] + solve(i, j + 1);
^
prog.cpp:25:8: note: declared here
string solve(int i, int j,int n,int m){
^
prog.cpp:36:41: error: too few arguments to function 'std::string solve(int, int, int, int)'
string rtt=a[i][j] + solve(i + 1, j);
^
prog.cpp:25:8: note: declared here
string solve(int i, int j,int n,int m){
^
prog.cpp:42:31: error: too few arguments to function 'std::string solve(int, int, int, int)'
string s11=solve(i, j + 1);
^
prog.cpp:25:8: note: declared here
string solve(int i, int j,int n,int m){
^
prog.cpp:43:31: error: too few arguments to function 'std::string solve(int, int, int, int)'
string s22=solve(i + 1, j);
^
prog.cpp:25:8: note: declared here
string solve(int i, int j,int n,int m){
^
stdout