迷宫最短路径 c++

Question

我需要计算从一个起点到另一个终点的距离和路径。http://coliru.stacked-crooked.com/a/b15078829f49df3c

int pathExists(char maze[][10], int sr, int sc, int er, int ec, int distance, int direction) {
    /*if(maze[sr][sc] != '.') . es visitable, x pared
        return 0;
 */
 int lmin=99, l;
    if(maze[sr][sc] != '.') //You cannot visit it, or is wall or is @ visited
        return 0;
    if(sr == er  &&  sc == ec) {
        display(maze); 
        cout << "Distance to end point is:  " << distance << endl; 
        //if ( lmin==l) PathBueno = PathInt;
        for (int i = 0; i < PathInt.size(); i++) {
            cout << PathInt[i];
            }
        return distance;
    }
    /*
    if(distance == 15) {
        cout << "Cant make it in 15 steps" << endl;
        return 0;
    }
    */
   // path.push_back(vertex);
    //Path.append(direction);
    PathInt.push_back(direction);
    maze[sr][sc] = '@';  // anything non-'.' will do

    //Row --  Norte
    l = pathExists(maze, sr - 1, sc, er, ec, distance + 1,1);
    if(l > 0 && l<lmin) {
        lmin = l; 
       // Path.append("N");
    }
    //Row ++  Sur
    l = pathExists(maze, sr + 1, sc, er, ec, distance + 1,2);
    if(l > 0 && l<lmin) {
        lmin = l; 
        //Path.append("S");
    }
    //Column --  Oeste
    l = pathExists(maze, sr, sc - 1, er, ec, distance + 1,3);
    if(l > 0 && l<lmin) 
        {
        lmin = l; 
        //Path.append("W");
    }
    //Column ++  Este
    l = pathExists(maze, sr, sc + 1, er, ec, distance + 1,4);
    if(l > 0 && l<lmin) 
    {
        lmin = l; 
        //Path.append("E");
    }
    maze[sr][sc] = '.'; //restore
    PathInt.pop_back();
    //if ( Path.size() > 2) Path.erase(Path.size() - 1);
    return lmin;
}

我一直在尝试很多事情。但是我无法打印或保存PathGood从一个点到另一个点的最短路径。在示例中，我想从 8.4 移动到 8.1...因此，最短路径有 3 步的距离，路径将是 EEE 或 333(假设 3 是 EAST(。

可验证的示例：

int main() {
    char maze[10][10] = {
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {'X', '.', '.', '.', '.', '.', '.', '.', '.', 'X'},
        {'X', '.', 'X', 'X', 'X', 'X', '.', 'X', 'X', 'X'},
        {'X', '.', '.', 'X', '.', 'X', '.', '.', '.', 'X'},
        {'X', '.', '.', 'X', '.', '.', '.', 'X', '.', 'X'},
        {'X', '.', 'X', 'X', '.', 'X', 'X', 'X', '.', 'X'},
        {'X', '.', 'X', '.', '.', '.', '.', 'X', 'X', 'X'},
        {'X', '.', '.', 'X', 'X', '.', 'X', 'X', '.', 'X'},
        {'X', '.', '.', '.', '.', '.', '.', '.', '.', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}
    };
    Path.clear();
    int  slen = pathExists(maze,8,4, 8, 1,0,0); 


    if(slen) {
        cout << "Solvable in "<<slen<<" steps !" << endl;
    //  cout << "Complete path is : " << Path;
    //    std::cout << "Complete path is : " << PathGood;
    }
    else
        cout << "Out of luck!" << endl;
    cin.get();
    //int len, i;
  /*  len = (int)strlen(string);
        for (int i = 0; i < PathBueno.size(); i++) {
            cout << PathBueno[i];
            }*/
}

我试图在吃豆人游戏中给鬼魂一些 IA。所以我需要知道最短的步距(避开墙壁(，然后开始移动。

任何帮助将不胜感激...

顺便说一句，我正在尝试使用DFS，我认为BFS会更有效率，所以如果有人可以帮助将其转换为BFS..(BFS确实比DFS更好(

现在我知道什么是更好的解决方案，但我不知道该采取哪个方向，因为程序可以存储最佳路径。

附注：

我开始尝试使用字符串和附加字符以及"N"、"W"、"S"等等......

Answer 1

问题是你没有存储最短路径(PathMin？

解决此问题

的方法不止一种。在代码中，pathExists返回一个int，该是最短路径的长度。相反，它可以返回最短路径vector<int>。

我认为BFS

比DFS更适合这个任务;将此代码转换为BFS将很困难。我建议你保持一个位置的向量，就像一队搜索者从起点向外穿过迷宫一样。搜索者轮流移动;当搜索者可以进行多个移动时，它会分成多个搜索者;当搜索者无法移动时，它就会死亡;当搜索者到达目的地时，搜索结束。

Answer 2

感谢@Beta但是经过大量测试后，我遇到了这个完美的结果：

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <map>
using namespace std;
//using String = char *;
std::string Path;
std::string PathGood;
vector<int> PathInt;
vector<int> PathBueno;
std::map < int, vector<int>> lista; 
template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
    out << "[";
    size_t last = v.size() - 1;
    for(size_t i = 0; i < v.size(); ++i) {
        out << v[i];
        if (i != last) 
            out << ", ";
    }
    out << "]";
    return out;
}
/*std::map<char,int> mymap;
  // first insert function version (single parameter):
  mymap.insert ( std::pair<char,int>('a',100) );
  mymap.insert ( std::pair<char,int>('z',200) );
  ret = mymap.insert ( std::pair<char,int>('z',500) );
  if (ret.second==false) {
    std::cout << "element 'z' already existed";
    std::cout << " with a value of " << ret.first->second << 'n';
  }
 */
void display(char maze[][10]) {
    for(int i = 0; i < 10; i++) {
        copy(maze[i], maze[i] + 10, ostream_iterator<char>(cout, ""));
        cout << endl;
    }
}

int pathExists(char maze[][10], int sr, int sc, int er, int ec, int distance, int direction) {
    /*if(maze[sr][sc] != '.') . es visitable, x pared
        return 0;
 */
 int lmin=99, l;
    if(maze[sr][sc] != '.') //You cannot visit it, or is wall or is @ visited
        return 0;
    if(sr == er  &&  sc == ec) {
        display(maze); 
        cout << "Distance to end point is:  " << distance << endl;
        cout << "Ultima direccion ess:  " << direction << endl; 
        //if ( lmin==l) PathBueno = PathInt;
        PathInt.push_back(direction);
        lista.insert ( std::pair<int,vector<int>>(distance,PathInt));
        PathInt.pop_back();
        return distance;
    }
    /*
    if(distance == 15) {
        cout << "Cant make it in 15 steps" << endl;
        return 0;
    }
    */
   // path.push_back(vertex);
    //Path.append(direction);
    PathInt.push_back(direction);
    maze[sr][sc] = '@';  // anything non-'.' will do

    //Row --  Norte
    l = pathExists(maze, sr - 1, sc, er, ec, distance + 1,1);
    if(l > 0 && l<lmin) {
        lmin = l; 
       // Path.append("N");
    }
    //Row ++  Sur
    l = pathExists(maze, sr + 1, sc, er, ec, distance + 1,2);
    if(l > 0 && l<lmin) {
        lmin = l; 
        //Path.append("S");
    }
    //Column --  Oeste
    l = pathExists(maze, sr, sc - 1, er, ec, distance + 1,3);
    if(l > 0 && l<lmin) 
        {
        lmin = l; 
        //Path.append("W");
    }
    //Column ++  Este
    l = pathExists(maze, sr, sc + 1, er, ec, distance + 1,4);
    if(l > 0 && l<lmin) 
    {
        lmin = l; 
        //Path.append("E");
    }
    maze[sr][sc] = '.'; //restore
    PathInt.pop_back();
    //if ( Path.size() > 2) Path.erase(Path.size() - 1);
    return lmin;
}

int main() {
    char maze[10][10] = {
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {'X', '.', '.', '.', '.', '.', '.', '.', '.', 'X'},
        {'X', '.', 'X', 'X', 'X', 'X', '.', 'X', 'X', 'X'},
        {'X', '.', '.', 'X', '.', 'X', '.', '.', '.', 'X'},
        {'X', '.', '.', 'X', '.', '.', '.', 'X', '.', 'X'},
        {'X', '.', 'X', 'X', '.', 'X', 'X', 'X', '.', 'X'},
        {'X', '.', 'X', '.', '.', '.', '.', 'X', 'X', 'X'},
        {'X', '.', '.', 'X', 'X', '.', 'X', 'X', '.', 'X'},
        {'X', '.', '.', '.', '.', '.', '.', '.', '.', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}
    };
    Path.clear();
    int  slen = pathExists(maze,5,4, 3, 1,0,0); 


    if(slen) {
        cout << "Solvable in "<<slen<<" steps !" << endl;
    //  cout << "Complete path is : " << Path;
    //    std::cout << "Complete path is : " << PathGood;
    }
    else
        cout << "Out of luck!" << endl;
    cin.get();
    // showing contents:
  std::map<int,std::vector<int>>::iterator it = lista.begin();
  std::cout << "Mi lista contains:n";
  for (it=lista.begin(); it!=lista.end(); ++it)
    std::cout << it->first << " => " << it->second << 'n';
  int direccionb = lista.find(slen)->second[1];
  cout << "La direccion buena de la buena es :" << direccionb << endl;
}