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);
}
 
double dist(int x, int y){
    n = n-x;
    y = n-y;
    return sqrt(pow(x, 2) + pow(y, 2));
}
 
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;
        }
    }
 
    auto nxt = new map<double,tuple<short,short,string, vector<char>>>();
 
    nxt->insert({0,{0,0,"",{}}});
 
    int x;
    int y;
    string len;
    vector<char> jono;
 
    while(!nxt->empty()){
        auto iter = nxt->begin();
        auto tup = iter->second;
        x = get<0>(tup);
        y = get<1>(tup);
        len = get<2>(tup);
        jono = get<3>(tup);
 
        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;
            break;
        }
 
        nxt->insert({dist(x-1, y), {x-1, y, len, jono}});
        nxt->insert({dist(x+1, y), {x+1, y, len, jono}});
 
        nxt->insert({dist(x, y+1), {x, y+1, len, jono}});
        nxt->insert({dist(x, y-1), {x, y-1, len, jono}});
    }
 
    step(0,0, "", {});
    for (const auto &item : shortestVec){
        cout << item;
    }
 
    flush(std::cout);
}

Test 1

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED