Submission by @naan112358

#include <bits/stdc++.h>
using namespace std;

namespace CoiL {
    // {{{
    #ifdef DEBUG
    # define dump(x) std::cerr << "\e[33mdump@" << __LINE__ << " : " << #x << " = " << (x) << "\e[0m" << std::endl;
    # define mesg(m) std::cerr << "\e[36mmesg@" << __LINE__ << " : " << (m) << "\e[0m" << std::endl;
    # define debug if (true)
    #else
    # define NDEBUG
    # define dump(x)
    # define mesg(m)
    # define debug if (false)
    #endif

    using Z = int;
    inline Z getz() {
        Z n;
        std::cin >> n;
        return n;
    }
    #define rep(i, n) for (decltype(n) i = 0; i < (n); i++)
    #define all(c) std::begin(c), std::end(c)
    void accelerate_IO() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
    // }}}
    Z n, h;
    vector<vector<Z>> field;

    using pos = pair<int, int>;

    inline bool is_valid(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }

//for tiny...
    pair<int, string> dfs(set<pos> &visited, string const &path, int x, int y, int accum) {
        if (x == n - 1 && y == n - 1)
            return {abs(accum), path};
        constexpr int dx[] = {1, 0, -1, 0},
                dy[] = {0, -1, 0, 1};
        constexpr char dir[] = "SWNE";
        int best = INT_MAX;
        string best_path = "";
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i],
                    ny = y + dy[i];
            if (visited.count({nx, ny}) || !is_valid(nx, ny))
                continue;
            visited.emplace(nx, ny);
            int trial;
            string trial_path;
            tie(trial, trial_path) = dfs(visited, path + dir[i], nx, ny, accum + field[nx][ny]);
            if (trial < best) {
                best = trial;
                best_path.swap(trial_path);
            }
            visited.erase({nx, ny});
        }
        return {best, best_path};
    }

    int main(int _n) {
        n = _n;
        accelerate_IO();
        field.resize(n);
        for (auto& row : field) {
            row.resize(n);
            for (auto& v : row)
                v = getz();
        }
        set<pos> init = {{0, 0}};
        cout << dfs(init, "", 0, 0, field[0][0]).second << std::endl;
    }
}

namespace Naan {
    int main(unsigned long W, unsigned long H) {
        constexpr unsigned long N = 6500;
        vector<vector<long>> n(W, vector<long>(H));
        for (auto &i : n)for (auto &j : i)cin >> j;

        vector<vector<bitset<N * 2>>> dp(W, vector<bitset<N * 2>>(H));
        dp[0][0][N + n[0][0]] = true;
        for (unsigned long i = 1; i < W; ++i)
            dp[i][0] = n[i][0] < 0 ? dp[i - 1][0] >> (-n[i][0]) : dp[i - 1][0] << (n[i][0]);
        for (unsigned long i = 1; i < H; ++i)
            dp[0][i] = n[0][i] < 0 ? dp[0][i - 1] >> (-n[0][i]) : dp[0][i - 1] << (n[0][i]);
        for (unsigned long i = 1; i < W; ++i)
            for (unsigned long j = 1; j < H; ++j)
                dp[i][j] = n[i][j] < 0 ? (dp[i - 1][j] | dp[i][j - 1]) >> (-n[i][j]) : (dp[i - 1][j] | dp[i][j - 1])
                        << n[i][j];

        long ans{numeric_limits<long>::max()};
        auto k = dp.back().back();
        for (unsigned long i = 0; i < 2 * N; ++i)
            if (k[i] && abs(ans) > max(i, N) - min(i, N))
                ans = static_cast<long>(i - N);

        string answerstring;
        for (long p = W - 1, q = H - 1, now = ans; p || q;) {
            now -= n[p][q];
            if (p && dp[p - 1][q][now + N]) {
                answerstring.push_back('S');
                --p;
            } else {
                answerstring.push_back('E');
                --q;
            }
        }
        reverse(answerstring.begin(), answerstring.end());
        cout << answerstring << endl;
        return 0;
    }
}

int main(){
    unsigned long H, W;
    cin >> H >> W;
    if(H <= 5){
        CoiL::main(H);
    }else{
        Naan::main(H, W);
    }
}

Battle History