1

Нужно написать программу, которая находит самый быстрый путь из одной точки к другой. Есть массив, заполненный рандомно 0 и 1. 0 — это свободное место; 1 — это шарик. Нужно перетянуть указанный шарик в указанную точку по самому быстрому пути. Количество строк, столбцов, координаты шарика и конечной точки считываются из файла. Я сделал заполнение массива из указанных данных в файле и пока что явно (в коде) шарик и конечную точку. Помогите создать алгоритм.

#include <iostream>
#include <cstdlib>
#include <ctime> // содержит time()
#include <fstream>
using namespace std;
int** arr;
int used[1][1];
int xk = 2, yk = 4;
int ab(int x, int y) {
    if (arr[x][y] == -1){
        return 0;// сюда нельзя
    }
    if ((x == xk) && (y = yk)){
        cout << "I go to nahyi";
        return 1;
    }
    if (!used[x - 1][y]){
        used[x - 1][y] = 1;
        if (ab(x - 1, y)) return 1;
        used[x - 1][y] = 0;
    }

    if (!used[x + 1][y]){
        used[x + 1][y] = 1;
        if (ab(x + 1, y)) return 1;
        used[x + 1][y] = 0;
    }

    if (!used[x][y - 1]){
        used[x][y - 1] = 1;
        if (ab(x, y - 1)) return 1;
        used[x][y - 1] = 0;
    }

    if (!used[x][y + 1]){
        used[x][y + 1] = 1;
        if (ab(x, y + 1)) return 1;
        used[x][y + 1] = 0;
    }
    return 0; //отсюда нельзя выйти
}

int main(){
    ifstream texts("text.txt");
    if (!texts){
        cout << "FIle not found";
    }
    int a;
    texts >> a;
    cout << a;
    int b;
    texts >> b;
    cout << b;
    arr = new int*[a];
    for (int l = 0; l < a; l++)
    {
        arr[l] = new int[b];
    }
    srand(time(NULL));
    for (int i = 0; i < a; i++){
        for (int j = 0; j < b; j++){
            arr[i][j] = rand() % 2;
            if (arr[1][1] == 0)
            {
                arr[1][1] = 1;
            }
            if (arr[4][2] == 1)
            {
                arr[4][2] = 0;
            }

        }
    }
    for (int i = 0; i < a; i++){
        cout << endl;
        for (int j = 0; j < b; j++){

            cout << " " << arr[i][j] << " ";

        }
    }
    cin.get();
}
1
  • Для перемещения по сетке есть куча алгоритмов поиска пути pathfinding, в частности очень много статей по алгоритму A* с визуализацией работы.
    – Alex Krass
    22 мая 2018 в 11:05

1 ответ 1

3

Вам нужен алгоритм поиска кратчайшего пути на графе, например, поиск в ширину

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.