/*! @file c.cc @brief Solves "The Secret Number" ( http://www.u-aizu.ac.jp/conference/ACM/results/C.html ) @author Yuta Kitamura @date 2005-04-09 */ // start 18:15 // end 18:56 #include #include using std::cout; using std::cin; using std::endl; using std::string; typedef unsigned int uint; bool num_less(const string& s1, const string& s2) { if (s1.length() != s2.length()) return s1.length() < s2.length(); else return s1 < s2; } void remove_leading_zeros(string& s) { if (!s.empty()) { string::size_type pos = s.find_first_not_of('0'); if (pos < s.length()) s = s.substr(s.find_first_not_of('0')); else s = ""; } return; } string calc_secret_number(string** table, const char* const* matrix, uint x, uint y, uint w, uint h) { if (!table[y][x].empty()) return table[y][x]; string ans; if ('0' <= matrix[y][x] && matrix[y][x] <= '9') { string r = (x + 1 < w) ? calc_secret_number(table, matrix, x+1, y, w, h) : ""; string d = (y + 1 < h) ? calc_secret_number(table, matrix, x, y+1, w, h) : ""; if (num_less(r, d)) ans = string(1, matrix[y][x]) + d; else ans = string(1, matrix[y][x]) + r; } table[y][x] = ans; return ans; } int main() { while (cin) { uint w, h; cin >> w >> h; if (w == 0 && h == 0) break; char** matrix = new char*[h]; string** table = new string*[h]; for (uint i = 0; i < h; ++i) { matrix[i] = new char[w]; table[i] = new string[w]; } for (uint y = 0; y < h; ++y) for (uint x = 0; x < w; ++x) cin >> matrix[y][x]; for (uint y = 0; y < h; ++y) for (uint x = 0; x < w; ++x) calc_secret_number(table, matrix, x, y, w, h); for (uint y = 0; y < h; ++y) for (uint x = 0; x < w; ++x) remove_leading_zeros(table[y][x]); string max; for (uint y = 0; y < h; ++y) for (uint x = 0; x < w; ++x) if (num_less(max, table[y][x])) max = table[y][x]; cout << max << endl; for (uint i = 0; i < h; ++i) { delete[] matrix[i]; delete[] table[i]; } delete[] matrix; delete[] table; } return 0; }