Suunnistus

#include<bits/stdc++.h>
#define F0R(i, n) for (i = 0; i < n; ++i)
#define FOR(i, l, r) for (i = l; i < r; ++i)
#define pii pair<int, int>
using namespace std;

const int N = 501;
const int mx = 1000000000;
int grid[N][N]; // -1 = obstacle, 0 = start, path, 10 = end, 1-9: controls
int dis[N][N];
int vis[N][N];
int n, m, k;
int dif[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int bfs(pii st, pii en) {
    int i, j;
    F0R (i, N) {
        F0R (j, N) vis[i][j] = 0;
    }

    queue<pair<pii, int>> q;
    q.push({st, 0});

    int a, b, d, x, mn = mx; pii p;
    while (!q.empty())  {
        tie(p, d) = q.front();
        tie(a, b) = p;
        q.pop();

        F0R (x, 4) {
            i = a+dif[x][0]; j = b+dif[x][1];
            if (i < 0 || i >= n) continue;
            if (j < 0 || j >= m) continue;
            if (vis[i][j]) continue;
            vis[i][j] = true;
            if (grid[i][j] == -1) continue;

            if (i==en.first && j==en.second) {
                mn = min(mn, d+1);
                continue;
            }
            q.push({{i, j}, d+1});
        }
    }
    return mn;
}

int main() {
    memset(grid, -1, sizeof(grid));
    memset(vis, 0, sizeof(vis));

    int i, j;
    cin >> n >> m >> k;

    char ch;
    pii start = {0, 0}, en;
    vector<pii> control(k, {-1, -1});
    F0R (i, n) {
        F0R (j, m) {
            cin >> ch;
            dis[i][j] = mx;
            if (ch == '#') grid[i][j] = -1;
            else if (ch == '.') grid[i][j] = 0;
            else if (ch == 'S') {
                grid[i][j] = 0;
                start = {i, j};
                dis[i][j] = 0;
            }
            else if (ch == 'E') {
                en = {i, j};
                grid[i][j] = 10;
            }
            else {
                grid[i][j] = int(ch-'0');
                control[ch-'1'] = {i, j};
            }
        }
    }


    int t;
    if (k == 0) {
        int length = bfs(start, en);
        if (length == mx) cout << "-1";
        else cout << length;
        return 0;
    }

    if (control[0].first == -1 && control[0].second == -1) {
        cout << "-1\n";
        return 0;
    }
    int length = bfs(start, control[0]);
    if (length == mx) {
        cout << "-1";
        return 0;
    }
    control.push_back(en);
    FOR (i, 1, k+1) {
        if (control[i].first == -1 && control[i].second == -1) {
            cout << "-1\n";
            return 0;
        }
        t = bfs(control[i-1], control[i]);
        if (t == mx) {
            cout << "-1"; return 0;
        }
        length += t;
    }
    cout << length;
}

Test 1

Group: 3

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 2, 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: WRONG ANSWER

Test 16

Group: 3

Verdict: WRONG ANSWER

Test 17

Group: 2, 3

Verdict: ACCEPTED