Suunnistus

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
string g[1010];
pair<int, int> st, en;
set<int> check;
vector<pair<int,int>> nums[10];
int e[10][1010][1010]; //etaisyydet
int z[10][1010][1010]; //kattoo onko kayty

int to_int(char c){
    return (int)c - 48;
}

char to_char(int x){
    return (char)(x + 48);
}

void dij(priority_queue<pair<int, pair<int,int>>>* q, int x, int dist, int i, int j){
    if (e[x][i][j] == -1 || dist + 1 < e[x][i][j]){
        e[x][i][j] = dist + 1;
        (*q).push({-(dist + 1), {i, j}});
    }
}

void dfs(int x, char c){ // x: nykynen numeor, char c: char jota etitään

    priority_queue<pair<int, pair<int,int>>> q; //muista että priority_queue järjestää isoimman ensimmäiseksi.

    if (x == 0) {
        e[0][st.first][st.second] = 0;
        q.push({0, st});
    }
    else{
        for(pair<int, int> i : nums[x]){
            if(e[x-1][i.first][i.second] == -1) continue;

            e[x][i.first][i.second] = e[x-1][i.first][i.second];
            q.push({-e[x][i.first][i.second], i});
        }
    }
    while(!q.empty()){
        int dist = -q.top().first; pair<int,int> l = q.top().second;
        q.pop();

        if(z[x][l.first][l.second]) continue;
        z[x][l.first][l.second] = 1;

        if (l.second - 1 >= 0 && g[l.first][l.second - 1] != '#') dij(&q, x, dist, l.first, l.second - 1); // vasen
        if (l.second + 1 < m && g[l.first][l.second + 1] != '#') dij(&q, x, dist, l.first, l.second + 1);//oikea

        if (l.first - 1 >= 0 && g[l.first - 1][l.second] != '#') dij(&q, x, dist, l.first - 1, l.second); //ylos
        if (l.first + 1 < n && g[l.first + 1][l.second] != '#') dij(&q, x, dist, l.first + 1, l.second); //alas

    }
}

int main(){

    cin >> n >> m >> k;
    
    for(int i = 0; i < n; i++) cin >> g[i];
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 1010; j++){
            for(int k = 0; k < 1010; k++){
                e[i][j][k] = -1;
            }
        }
    }

    st = {-1, -1};
    en = {-1, -1};

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if (g[i][j] == 'S') st = {i, j};
            else if (g[i][j] == 'E') en = {i, j};
            else if (g[i][j] != '#' && g[i][j] != '.'){
                check.insert(to_int(g[i][j]));
                nums[to_int(g[i][j])].push_back({i, j});
            }
        }
    }
    nums[0].push_back(st);

    for(int i = 0; i < k; i++) dfs(i, to_char(i + 1));
    dfs(k, 'E');

    int ans = e[k][en.first][en.second];
    cout << ans << endl;
}

Test 1

Group: 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 2, 3

Verdict: ACCEPTED