Сохранение координат пути в рекурсивном лабиринте?

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

Это рекурсивная функция

void Solve_Maze(int coorx,int coory) {
    if((coorx>=0)&&(coorx<l)&&(coory>=0)&&(coory<w)) {
        if((Map[coorx][coory]==Start)||(Map[coorx][coory]==path)) {
            Map[coorx][coory]=visited;
            Solve_Maze(coorx+1,coory);
            Solve_Maze(coorx-1,coory);
            Solve_Maze(coorx,coory+1);
            Solve_Maze(coorx,coory-1);
        }else if(Map[coorx][coory]==End) {
            delete Map;
            Solved=true;
        }
    }
}

После добавления вектора для хранения координат я получил этот вывод

(1,2)
(2,2)
(3,2)
(4,2)
(5,2)
(6,2)
(7,2)
(8,2)
(9,2)
(7,3)
(7,4)
(7,5)
(7,6)
(8,6)
(8,7)
(9,7)
(10,7)

Он хранит все координаты, но даже хранит координаты пути, по которому мы не хотим идти ((7,2)(8,2)(9,2) и затем обратно к (7,3)). Есть ли способ сохранить только кратчайший путь?


c++ coordinates recursion maze
person Jake Runzer    schedule 20.05.2012    source источник
comment
Что-то, что направит вас в правильном направлении: std::vector и std::vector::push_back.   -  person chris    schedule 20.05.2012
comment
Ваш алгоритм выглядит хорошо, поскольку он должен найти кратчайший путь, если его правильно настроить. Я согласен с предложением Криса и предлагаю вам изменить прототип метода на что-то вроде std::vector Solve_Maze(int coorx, coory, std::vector path).   -  person jedwards    schedule 20.05.2012
comment
Должен ли я иметь два вектора (один для значений x и один для значений y)? И будет ли это слово с рекурсивным аспектом проблемы, потому что, если алгоритм ищет другой путь, а не кратчайший, координаты также будут сохранены.   -  person Jake Runzer    schedule 20.05.2012

Ответы (2)


arrow_upward
2
arrow_downward

Вот как вы можете отслеживать координаты решения с помощью вектора:

#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int w = 10, l = 10;
const char Start = 'S', Path = ' ', End = 'E', Visited = '.', Solution = '*';

char Map[w][l + 1] =
{
    { "  #  # #  " },
    { " S   #  # " },
    { " ###      " },
    { "   #   #  " },
    { "    #   # " },
    { "#        #" },
    { "    ###   " },
    { "  ##E ##  " },
    { "  #       " },
    { "   ##### #" },
};

int Solved = false;
vector<pair<int,int> > SolutionCoors;

void PrintMap()
{
    int x, y;

    for (y = 0; y < w; y++)
    {
        for (x = 0; x < l; x++)
            cout << Map[y][x];

        cout << endl;
    }
}

void Solve_Maze(int CoorX, int CoorY)
{
    if (CoorX >= 0 && CoorX < l && CoorY >= 0 && CoorY < w && !Solved)
    {
        SolutionCoors.push_back(make_pair(CoorX, CoorY)); // Store potential solution

        if (Map[CoorY][CoorX] == Start || Map[CoorY][CoorX] == Path)
        {
            Map[CoorY][CoorX] = Visited;

            Solve_Maze(CoorX + 1, CoorY);
            Solve_Maze(CoorX - 1, CoorY);
            Solve_Maze(CoorX, CoorY + 1);
            Solve_Maze(CoorX, CoorY - 1);
        }
        else if (Map[CoorY][CoorX] == End)
            Solved = true;

        if (!Solved)
            SolutionCoors.pop_back();
    }
}

int main()
{
    PrintMap();

    Solve_Maze(1, 1);

    if (Solved)
    {
        for (vector<pair<int,int> >::iterator it = SolutionCoors.begin();
             it != SolutionCoors.end();
             it++)
        {
            cout << "(" << it->first << "," << it->second << ")" << endl; // Print solution coords
            Map[it->second][it->first] = Solution; // Also mark on the map
        }

        PrintMap();
    }

    return 0;
}

Выход:

  #  # #  
 S   #  # 
 ###      
   #   #  
    #   # 
#        #
    ###   
  ##E ##  
  #       
   ##### #
(1,1)
(2,1)
(3,1)
(4,1)
(4,2)
(5,2)
(6,2)
(6,3)
(5,3)
(5,4)
(6,4)
(7,4)
(7,5)
(8,5)
(8,6)
(9,6)
(9,7)
(8,7)
(8,8)
(7,8)
(6,8)
(5,8)
(4,8)
(4,7)
  #  #.#..
 ****#..#.
 ###***...
   #.**#..
    #***#.
#      **#
    ### **
  ##* ##**
  #.*****.
   ##### #

Также обратите внимание, что мой Map[][] имеет обратные координаты.

person Alexey Frunze    schedule 20.05.2012

arrow_upward
0
arrow_downward

Вам нужно сделать стек явным, что теперь он неявный в вызовах процедуры Solve_Maze, и скопировать из стека в вектор решения, когда вы достигнете Solved=true, если длина текущего пути меньше, чем длина ранее сохраненного (если есть) . Конечно, нажмите coorx,coory при входе в процедуру, нажмите их при выходе (не заботьтесь об изменении состояния).

Помимо внешней переменной, если тип «стек» (вы можете использовать массив, если вы не используете стандартные библиотеки), вы можете связать вместе coorx, coory в структуру и передать указатель на них при выделении в Solve_Maze. Но это сильно меняет код: намного проще обойти стек...

person CapelliC    schedule 20.05.2012