在递归迷宫解算器中保存路径坐标？

我有一个递归的迷宫解算器算法，可以成功地通过迷宫的方式。唯一的问题是我找不到一种方法来保存起点和终点之间的最短路径。我将如何保存最短路径的坐标？在递归迷宫解算器中保存路径坐标？

这是递归函数

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））。有没有一种方法可以存储最短路径？

来源

2012-05-20 Jake Runzer

东西让你在正确的方向：'std :: vector'和'std :: vector :: push_back'。 – chris

你的算法看起来不错，它应该找到适当调整的最短路径。我同意克里斯的建议，并进一步建议你将方法原型改为'std :: vector Solve_Maze（int coorx，coory，std :: vector path）'。 – jedwards

我必须有两个向量（一个用于x值，一个用于y值）？这个词与问题的递归方面，因为如果算法搜索不同的路径，然后最短的坐标也将被保存。 –

这里是你如何跟踪解决方案的使用矢量坐标：

#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[][]已颠倒坐标。

来源

2012-05-20 06:49:56

如果当前路径的长度小于先前保存的长度，则需要明确显示堆栈，现在它隐含在调用Solve_Maze调用中，并且从堆栈复制到解向量时为Solved=true （如果有的话）。进入程序时当然推coorx,coory，退出时弹出它们（不关心状态变化）。

除了类型为'stack'的外部变量（如果不使用std库，你可以使用数组），你可以将coorx和coory绑定在一个结构体中，并在分配时将指针传递给它们进入Solve_Maze。但是，这改变了代码很多：它容易得多绕过堆...

来源

2012-05-20 05:35:56 CapelliC

在递归迷宫解算器中保存路径坐标？

回答

相关问题