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

Для нахождения кратчайшего пути в лабиринте, где можно двигаться только вперед и направо, мы можем использовать модифицированный алгоритм поиска в ширину (BFS).

1. Зададим лабиринт в виде двумерного массива, где каждая ячейка будет представлять собой либо стену, либо проход. Пример:

int maze[N][M] = {
    {1, 0, 1, 1, 1},
    {1, 0, 1, 0, 1},
    {1, 1, 1, 0, 1},
    {0, 0, 0, 0, 1},
    {1, 1, 1, 0, 1}
};

В данном примере 1 обозначает стену, а 0 - проход.

2. Создадим структуру для представления вершины графа (ячейки в лабиринте):

struct Cell {
    int x, y, dist;
};

3. Реализуем алгоритм BFS:

int shortestPath(int maze[N][M]) {
    bool visited[N][M] = {false};

    queue<Cell> q;
    q.push({0, 0, 0});
    visited[0][0] = true;

    while (!q.empty()) {
        Cell cell = q.front();
        q.pop();

        // Если дошли до конечной точки
        if (cell.x == N - 1 && cell.y == M - 1) {
            return cell.dist;
        }

        // Перемещаемся вправо
        if (cell.y + 1 < M && maze[cell.x][cell.y + 1] == 0 && !visited[cell.x][cell.y + 1]) {
            q.push({cell.x, cell.y + 1, cell.dist + 1});
            visited[cell.x][cell.y + 1] = true;
        }

        // Перемещаемся вперед
        if (cell.x + 1 < N && maze[cell.x + 1][cell.y] == 0 && !visited[cell.x + 1][cell.y]) {
            q.push({cell.x + 1, cell.y, cell.dist + 1});
            visited[cell.x + 1][cell.y] = true;
        }
    }

    return -1; // Путь не найден
}

4. Вызываем функцию shortestPath и получаем длину кратчайшего пути:

int shortestPathLength = shortestPath(maze);
if (shortestPathLength != -1) {
    cout << "Длина кратчайшего пути: " << shortestPathLength << endl;
} else {
    cout << "Кратчайший путь не найден" << endl;
}

Этот алгоритм находит кратчайший путь в лабиринте, двигаясь только вперед и направо, за время O(N*M), где N - количество строк в лабиринте, M - количество столбцов.