VK профильное задание

/*
    N - количество вершин в графе, M - количество рёбер в графе.
    В нашем случае N = sizeI * sizeJ, M = 2 * sizeI * sizeJ;

    Стандартная задача на поиск кратчайшего пути в лабиринте с восстановлением ответа, изначально хотел
    написать Дейкстру за O(NlogM) --> O(sizeI*sizeJ * log(sizeI * sizeJ)), но обратил внимание на
    маленькое ограничения веса ребра,поэтому предположил, что может существовать что-то быстрее Дейкстры.
    Погугля нашёл на codeforces блог про алгоритм 1-K BFS, который работает для графов с весом рёбер от 1 до K.

    Блог на codeforces: https://codeforces.net/blog/entry/88408?locale=ru&mobile=true

    1-K BFS. Алгоритм работает за O(9 * N + M) --> O(sizeI * sizeJ) по времени и по памяти.
*/

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false); // для ускорения ввода и вывода
    cin.tie(nullptr);

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int sizeI, sizeJ; cin >> sizeI >> sizeJ;
    cin.ignore();

    if(sizeI <= 0 || sizeJ <= 0){
        cerr << "Введены отрицательные или равные нулю размеры лабиринта";
        return 1; //возвращаю 1, что в этом случае аналогично вызову exit(1)
    }

    if(1LL * sizeI * sizeJ > 1'000'000LL){
        cerr << "Размер лабиринта слишком большой, не можем выделить столько памяти под массив";
        return 1;
    }

    vector<vector<int>> field(1 + sizeI + 1, vector<int>(1 + sizeJ + 1, 0));

    for(int i = 1; i <= sizeI; i++){
        string s; getline(cin, s);

        if(s.size() != sizeJ + sizeJ - 1){
            cerr << "Неправильный ввод данных в клетки лабиринта";
            return 1;
        }

        for(int ii = 0, j = 1; ii < s.size(); ii++){
            if(ii % 2 == 0){
                if('0' <= s[ii] && s[ii] <= '9'){
                    field[i][j] = s[ii] - '0';
                    j++;
                } else {
                    cerr << "Неправильный ввод данных в клетки лабиринта";
                    return 1;
                }
            } else if(s[ii] != ' '){
                    cerr << "Неправильный ввод данных в клетки лабиринта";
                    return 1;
            }
        }

    }

    int startI, startJ, finishI, finishJ;
    cin >> startI >> startJ >> finishI >> finishJ;

    startI++, startJ++, finishI++, finishJ++;

    if( startI < 1 || startJ > sizeJ || 1 > finishI || finishJ > sizeJ){
        cerr << "Коордианты клетки выходят за границы лабиринта";
        return 1;
    }

    if(field[startI][startJ] == 0){
        cerr << "Начальная точка находится в клетке со стеной";
        return 1;
    }

    if(field[finishI][finishJ] == 0){
        cerr << "Конечная точка находится в клетке со стеной";
        return 1;
    }

    vector<vector<char>> was(1 + sizeI + 1, vector<char>(1 + sizeJ + 1, 0));
    vector<vector<int>> dist(1 + sizeI + 1, vector<int>(1 + sizeJ + 1, INF));

    vector<queue<pair<int,int>>> q(10);
    q[0].push({startI, startJ});
    dist[startI][startJ] = field[startI][startJ];

    int szQueue = 1, curIndex = 0;

    while(szQueue > 0){
        while(q[curIndex % 10].empty()){
            curIndex++;
        }

        auto x = q[curIndex % 10].front();
        q[curIndex % 10].pop();
        szQueue--;

        int i = x.first, j = x.second;
        if(was[i][j]){
            continue;
        }

        was[i][j] = 1;

        for(int di = -1; di <= 1; di++){
            for(int dj = -1; dj <= 1; dj++){
                int ni = i + di, nj = j + dj;
                if(di * di + dj * dj == 1 && field[ni][nj] > 0 && dist[i][j] + field[ni][nj] < dist[ni][nj]){
                    dist[ni][nj] = dist[i][j] + field[ni][nj];
                    q[dist[ni][nj] % 10].push({ni, nj});
                    szQueue++;
                }
            }
        }
    }

    vector<pair<int,int>> ans;

    int curI = finishI, curJ = finishJ;
    while(curI != startI || curJ != startJ){
        ans.push_back({curI, curJ});

        bool flag = true;
        for(int di = -1; di <= 1 && flag; di++){
            for(int dj = -1; dj <= 1; dj++){
                int prevI = curI + di, prevJ = curJ + dj;
                if(di * di + dj * dj == 1 && field[prevI][prevJ] > 0 && dist[prevI][prevJ] + field[curI][curJ] == dist[curI][curJ]){
                    curI = prevI, curJ = prevJ;
                    flag = false;
                    break;
                }
            }
        }
    }

    ans.push_back({curI, curJ});
    reverse(ans.begin(), ans.end());

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i].first - 1 << ' ' << ans[i].second - 1 << '\n';
    }
    cout << '.';

    return 0;
}