Suunnistus

input/code.cpp: In function 'int main()':
input/code.cpp:145:37: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |         if (c > 48 && c < 58) flags[c].pb({x, y});
      |                                     ^
input/code.cpp:158:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |         for (ip p : flags[c])
      |                           ^

#include <bits/stdc++.h>

#define newl "\n"

#define pb push_back

#define X first
#define Y second

#define N 502

using namespace std;

typedef long long ll;

typedef pair<int, int> ip;
typedef pair<ll, ll> lp;

struct Move
{
    ip p;
    int d;
};

char m[N][N];
bool v[N][N];
bool visited[N * N];

int h, w, k;

vector<ip> adj[N * N];

int index(ip p)
{
    return p.Y * (w + 2) + p.X;
}

void clear_visited()
{
    for (int y = 1; y <= h; y++)
    for (int x = 1; x <= w; x++)
    {
        v[x][y] = false;
    }
}

bool valid(ip p)
{
    return v[p.X][p.Y] == false && m[p.X][p.Y] != '#';
}

void bfs(ip start, char target)
{
    queue<Move> q;

    q.push({start, 0});

    int start_index = index(start);

    while (q.size() > 0)
    {
        Move move = q.front(); q.pop();

        if (!valid(move.p)) continue;

        int x = move.p.X;
        int y = move.p.Y;
        int d = move.d;

        v[x][y] = true;

        if (m[x][y] == target)
        {
            adj[start_index].pb({index(move.p), d});
        }

        q.push({{x+1, y}, d+1});
        q.push({{x-1, y}, d+1});
        q.push({{x, y+1}, d+1});
        q.push({{x, y-1}, d+1});
    }

    clear_visited();
}

int dijkstra(ip start, ip end)
{
    priority_queue<ip, vector<ip>, greater<ip>> q;

    int start_index = index(start);
    int end_index = index(end);

    q.push({0, start_index});

    while (q.size() > 0)
    {
        ip p = q.top(); q.pop();

        int distance = p.first;
        int index = p.second;

        if (visited[index]) continue;

        visited[index] = true;

        if (index == end_index)
        {
            return distance;
        }

        for (ip p : adj[index])
        {
            q.push({distance + p.second, p.first});
        }
    }

    return -1;
}

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

    for (int y = 0; y < N; y++)
    for (int x = 0; x < N; x++)
    {
        m[x][y] = '#';
    }

    cin >> h >> w >> k;

    ip start, end;

    vector<ip> flags[128];

    for (int y = 1; y <= h; y++)
    for (int x = 1; x <= w; x++)
    {
        char c; cin >> c;

        if (c != '#') m[x][y] = c;
        if (c == 'S') start = {x, y};
        if (c == 'E') end =  {x, y};
        
        if (c > 48 && c < 58) flags[c].pb({x, y});
    }

    if (k == 0)
    {
        bfs(start, 'E');
        cout << dijkstra(start, end);
        exit(0);
    }

    bfs(start, '1');

    for (char c = '1'; c < '1' + k; c++)
        for (ip p : flags[c])
            bfs(p, c+1);
    
    for (ip p : flags['1' + k - 1])
        bfs(p, 'E');

    cout << dijkstra(start, end) << 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: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

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