Ruudukko

#include <bits/stdc++.h>

using namespace std;

char arr[500][500] = {{__INT8_MAX__}};

string w[500][500] = {""};

int n;

bool valid(int i){
    return i >= 0 && i < n;
}

bool sF = false;
string shortest = "";
vector<char> shortestVec;

void step(int x, int y, string len, vector<char> jono){
    len += arr[x][y];
    if(!w[x][y].empty() && len.length() >= w[x][y].length() && (len.length() > w[x][y].length() || len >= w[x][y])) return;
    w[x][y] = len;

    jono.emplace_back(arr[x][y]);
    if(x == n-1 && y == n-1){
        shortest = len;
        shortestVec = jono;
        return;
    }

    if(valid(x-1)) step(x-1, y, len, jono);
    if(valid(x+1)) step(x+1, y, len, jono);

    if(valid(y+1)) step(x, y+1, len, jono);
    if(valid(y-1)) step(x, y-1, len, jono);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    char b;
    for (int y = 0; y < n; ++y){
        for (int x = 0; x < n; ++x){
            cin >> b;
            arr[x][y] = b;
        }
    }

    list<tuple<short,short,string, vector<char>>> nxt = {};

    nxt.push_back({0,0,"",{}});

    int x;
    int y;
    string len;
    vector<char> jono;

    while(!nxt.empty()){
        auto elem = nxt.back();
        nxt.pop_back();
        x = get<0>(elem);
        y = get<1>(elem);
        len = get<2>(elem);
        jono = get<3>(elem);

        len += arr[x][y];
        if(!w[x][y].empty() && len.length() >= w[x][y].length() && (len.length() > w[x][y].length() || len >= w[x][y])) continue;
        w[x][y] = len;

        jono.emplace_back(arr[x][y]);
        if(x == n-1 && y == n-1){
            shortest = len;
            shortestVec = jono;
            continue;
        }

        if(valid(x-1)) nxt.emplace_back(x-1, y, len, jono);
        if(valid(x+1)) nxt.emplace_back(x+1, y, len, jono);

        if(valid(y+1)) nxt.emplace_back(x, y+1, len, jono);
        if(valid(y-1)) nxt.emplace_back(x, y-1, len, jono);
    }

    step(0,0, "", {});
    for (const auto &item : shortestVec){
        cout << item;
    }

    flush(std::cout);
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: RUNTIME ERROR

Test 7

Group: 2

Verdict: RUNTIME ERROR

Test 8

Group: 2

Verdict: RUNTIME ERROR

Test 9

Group: 2

Verdict: RUNTIME ERROR

Test 10

Group: 2

Verdict: RUNTIME ERROR

Test 11

Group: 3

Verdict: RUNTIME ERROR

Test 12

Group: 3

Verdict: RUNTIME ERROR

Test 13

Group: 3

Verdict: RUNTIME ERROR

Test 14

Group: 3

Verdict: RUNTIME ERROR

Test 15

Group: 3

Verdict: RUNTIME ERROR