Здравствуйте! Помогите составить алгоритм:
Программа: Навигатор
Описание: Работает с координатной плоскостью. Некоторые клетки в плоскости - стены.
Цель: Составить несколько маршрутов (в случае препятствий) и выбрать наикратчайший.
Принцип работы:
Для каждой клетки в файле прописаны идентификатор (возможно динамический), координаты, варианты перехода (влево, вверх, вправо, вниз). Если в данном направлении можно пойти то это 1 иначе 0. Пример строки: "1845024 +2,-2 1011" (можно пойти влево, вправо и вниз).
Если конечная координата слева то нужно идти влево, или вправо если конечная координата справа (сравнивание по координате х до препятствия), если туда нельзя пойти то следует построение 2-х путей-попытка обойти сверху или снизу. Если вниз или вверх нельзя пойти то 1-н из путей отдалится от конечной координаты на 1, если и вверх и вниз нельзя пойти то следует 1 путь - отдаление от конечной координаты. !Программа не должна возвращаться на ту клетку где была ранее, иначе это будет бесконечный цикл! В этих 2-х путях продолжать построение вниз и вверх до тех пор пока нельзя будет пойти влево (или вправо если конечная координата справа). Когда препятствие удалось обойти, нужно продолжить сравнивание по координате х...Когда x текущая будет = х конечная - проделать сравнивание по y (тот же скрипт, только вместо x-y -> исполнитель обходит препятствия слева и справа). Когда сравнивание по Y будет завершено, начать сравнивание по x !Возвращаться назад нельзя! После чего опять сравнивание по Y. проделывать до тех пор, пока не будет (x текущее=х конечное) и (y текущее =y конечное)... В итоге сравниваются полученные пути, выбирается наикратчайший...если таких путей несколько, то выбрать тот в котором по y переходов больше. Если таких путей несколько то рандомом. После этого исполнить переход по конечному пути.
Суть проблемы: Я не знаю как мне это осуществить: потоки, массивы или запись путей в файл. В целом я не знаю как построить такой алгоритм (КОД). Я только могу описать как это должно работать...
Что требуется: Помогите пожалуйста построить код, под мое описание.
P.S. На картинке представлено 4 возможных пути. Правый нижний - самый короткий, в нем 13 переходов.
