Как найти кратчайший путь в лабиринте, двигаться в котором можно только вперед и направо?

Question

[FaxWeb]

Решаю задачу на bfs - https://informatics.msk.ru/mod/statements/view.php...

Код написал вроде как корректный, но решение не проходит. Догадываюсь, что не проходит оно из-за проверки на то, что координаты нового "шага" уже присутствуют в векторе dist, из-за чего персонаж не может сделать круг чтобы развернуться. Данная проверка в коде:

if (dist[option.y][option.x] > dist[v.y][v.x] + 1){
    dist[option.y][option.x] = dist[v.y][v.x] + 1;
    q.push(option);
}

Код моего решения:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1E9;

struct Vertex {
    int y;
    int x;
    int dir; // 0-up, 1-right, 2-down, 3-left
    Vertex(int y, int x, int dir) : y(y), x(x), dir(dir) {}
};

vector<Vertex> getOptions(vs &g, Vertex v){
    int h = g.size(), w = g[0].size();
    vector<Vertex> options;
    vi dy = {-1, 0, 1, 0};
    vi dx = {0, 1, 0, -1};
    
    int ty = v.y + dy[v.dir];
    int tx = v.x + dx[v.dir];
    if (ty >= 0 && tx >= 0 && ty < h && tx < w && g[ty][tx] != 'X'){
        options.push_back({ ty, tx, v.dir });
    }

    ty = v.y + dy[(v.dir + 1) % 4];
    tx = v.x + dx[(v.dir + 1) % 4];
    if (ty >= 0 && tx >= 0 && ty < h && tx < w && g[ty][tx] != 'X'){
        options.push_back({ ty, tx, (v.dir + 1) % 4 });
    }

    return options;
}

int bfs(vs &g, pair<int, int> start){
    int h = g.size(), w = g[0].size();
    vector<vi> dist(h, vi(w, INF));
    queue<Vertex> q;

    dist[start.first][start.second] = 0;
    q.push({ start.first, start.second, 0 });

    while (!q.empty()){
        Vertex v = q.front();
        q.pop();

        if (g[v.y][v.x] == 'F'){
            return dist[v.y][v.x];
        }

        for (Vertex &option : getOptions(g, v)){
            if (dist[option.y][option.x] > dist[v.y][v.x] + 1){
                dist[option.y][option.x] = dist[v.y][v.x] + 1;
                q.push(option);
            }
        }
    }

    return -1;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    cin.ignore();

    vs g(n);
    pair<int, int> start;
    for (int y = 0; y < n; y++){
        getline(cin, g[y]);
        for (int x = 0; x < m; x++){
            if (g[y][x] == 'S') start = { y, x };
        }
    }

    cout << bfs(g, start);

    return 0;
}

Answer 1

[Wataru]

Вы правильно поняли, что у вас вершинами в гарфе являются клетка+направление, по которому пришли.
Но раз у вас вот это вершины, то вам и пометки о песещении вершины надо делать в трехмерном массиве. А начальных и финальных вершин у вас по 4 штуки: клетка x 4 направления (на самом деле, начинать достаточно только с 2 направлений, но неважно).

Comments

[FaxWeb]

Ошибку понял, изменил dist на трехмерный массив, теперь код учитывает и направление. Но решение прошло только 70% тестов, что-то все еще не так. И вообще, использование 3d массива считается нормой для такой задачи, или лучше стараться этого избегать и писать иначе?
Измененная функция bfs:

int bfs(vs &g, pair<int, int> start){
    int h = g.size(), w = g[0].size();
    vector<vector<vi>> dist(h, vector<vi>(w, vi(4, INF)));
    queue<Vertex> q;

    dist[start.first][start.second][0] = 0;
    q.push({ start.first, start.second, 0 });

    while (!q.empty()){
        Vertex v = q.front();
        q.pop();

        if (g[v.y][v.x] == 'F'){
            return dist[v.y][v.x][v.dir];
        }

        for (Vertex &option : getOptions(g, v)){
            if (dist[option.y][option.x][option.dir] > dist[v.y][v.x][v.dir] + 1){
                dist[option.y][option.x][option.dir] = dist[v.y][v.x][v.dir] + 1;
                q.push(option);
            }
        }
    }

    return -1;
}

[Wataru]

Похоже, ук вас проблема с начальным состоянием. В очередь надо сложить 4 направления.

И вообще, использование 3d массива считается нормой для такой задачи, или лучше стараться этого избегать и писать иначе?

Ну, одно измерение тут всего 4. Так что не очень-то оно и трехмерное. Если у вас пространство вершин такое, то по-другому никак. Если так глаза мозилит, то можно завести массив фиксированного размера с максимальными размерами в задаче. Или вообще сделать массив одномерным и вычислять индексы руками.

А в каких-нибудь задачах на DP иногда и 5-мерные массивы бывают.

[FaxWeb]

Wataru, точно, изменил начальное состояние для dist и q, и все тесты прошли, спасибо. Понял про массивы, ДП буду чуть позже изучать, там и узнаю всю красоту 5-мерных массивов судя по всему)