AOJ-1126 : The Secret Number

The Secret Number

英数字が敷き詰められた表を与えられる。
数字のマスから、隣接する数字のマスへ右か下に続けて移動出来る。(上と左に移動は禁止)
そのように、移動した時に作れる数字の中で、最大の数字を出力せよ。

解法としては、深さ優先探索+メモ化（メモ化再帰）。
深さ優先探索だけでもサンプルは解けるが、TLEになるので工夫が必要。

また、作った数字を整数などに変換してから比較しようとするとRuntime Errorになる。
テストデータにはものすごい大きな数字があるようで、long long 型でも厳しいようなので
文字列のままで比較出来る関数を作った。

// The Secret Number
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1126

#include<iostream>
#include<vector>

using namespace std;

int W, H;
vector<string> matrix;
vector<vector<string>> memo;

int dx[2] = {1, 0};
int dy[2] = {0, 1};

inline bool is_out_of_range(int x, int y) {
    return (x < 0 || x >= W || y < 0 || y >= H);
}

string cmp(string a, string b) {
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    return max(a, b);
}

string dfs(int x, int y) {
    if (is_out_of_range(x, y)) return "";
    if (!isdigit(matrix[y][x])) return "";
    if (memo[y][x] != "") return memo[y][x];

    string res = "";
    for (int d = 0; d < 2; ++d) {
        res = cmp(res, matrix[y][x] + dfs(x + dx[d], y + dy[d]));
    }
    memo[y][x] = res;
    return res;
}

int main() {
    while (cin >> W >> H && W) {
        matrix = vector<string>(H, ""); 
        memo.assign(H, vector<string>(W, ""));
        for (int h = 0; h < H; ++h) {
            cin >> matrix[h];
        }

        string ans = "";
        for (int y = 0; y < H; ++y) {
            for (int x = 0; x < W; ++x) {
                if (matrix[y][x] == '0' || !isdigit(matrix[y][x])) continue;
                ans = cmp(ans, dfs(x, y));
            }
        }

        cout << ans << endl;
    }
    return 0;
}