C++深度优先搜索例题：从迷宫中得出最短路径 |21xrx.com

C++深度优先搜索例题：从迷宫中得出最短路径

2023-07-04 14:54:02 深夜i -- --

C++ 深度优先搜索迷宫最短路径

C++是一门广泛应用于计算机编程领域的高级编程语言，它可以用于各种算法模型的实现，其中深度优先搜索是其中一种较经典的算法。在应用深度优先搜索时，我们可以求出一个图或者迷宫等数据结构中的最短路径。本文将以C++深度优先搜索例题为例，来讲解如何通过代码实现在一个迷宫中寻找最短路径的过程。

在进行深度优先搜索过程中，我们需要实现以下两个函数：

- 一个以当前状态作为参数，返回该状态相邻状态的函数。

- 一个以当前状态作为参数，返回该状态是否为终点的函数。

我们以以下迷宫为例：

1100 1110 0111 0010

其中0表示迷宫中的路，1表示墙。我们将以(0,0)作为起点，(3,2)作为终点，寻找从起点到终点的最短路径。

首先，我们需要实现一个“状态类”，用于存储迷宫搜索过程中的各种状态信息。在本例中，状态信息包括当前坐标和搜索路径长度。代码如下：


class State {
  public:
    int x;
    int y;
    int len;
    State(int x, int y, int l)
      this->x = x;
      this->y = y;
      this->len = l;
    
};

接下来，我们需要实现一个函数来返回当前状态的相邻状态。该函数将在搜索过程中被反复调用，直到找到终点。代码如下：


vector<State> getNextStates(State s, vector<vector<bool>> &visited, vector<vector<int>> &maze) {
  vector<State> next;
  int dx[] = -1;
  int dy[] = 0;
  for (int i = 0; i < 4; i++) {
    int nx = s.x + dx[i];
    int ny = s.y + dy[i];
    if (nx >= 0 && nx < maze.size() && ny >= 0 && ny < maze[0].size() && maze[nx][ny] == 0 && !visited[nx][ny]) {
      visited[nx][ny] = true;
      next.emplace_back(nx,ny,s.len+1);
    }
  }
  return next;
}

上述函数接受当前状态对象s、访问标记向量visit和迷宫vector > maze作为参数，返回当前状态可达的下一个状态对象集合。

接下来，我们需要实现另一个函数来判断当前状态是否为终点。代码如下：


bool isEndState(State s, int ex, int ey)
  return s.x == ex && s.y == ey;

该函数返回一个布尔值，表示当前所在状态对象是否为终点。

最后，我们需要实现一个主函数，通过调用上述两个函数来进行深度优先搜索，并输出找到的最短路径的长度。代码如下：


int search(int sx, int sy, int ex, int ey, vector<vector<int>> &maze) {
  vector<vector<bool>> visited(maze.size(),vector<bool>(maze[0].size(),false));
  stack<State> s;
  s.emplace(sx,sy,0);
  visited[sx][sy] = true;
  while (!s.empty()) {
    State curr = s.top();
    s.pop();
    if (isEndState(curr,ex,ey))
      return curr.len;
    
    vector<State> nexts = getNextStates(curr,visited,maze);
    for (int i = 0; i < nexts.size(); i++) {
      s.push(nexts[i]);
    }
  }
  return -1;
}

上述函数接受起点sx、sy坐标、终点ex、ey坐标和迷宫vector > maze作为参数，返回从起点到终点的最短路径长度。

最后，我们只需要在主函数中调用search函数，即可输出从起点到终点的最短路径长度。


int main() {
  vector<vector<int>> maze = {
    0,
    1,
    1,
    1
  };
  int sx = 0, sy = 0, ex = 3, ey = 2;
  int len = search(sx,sy,ex,ey,maze);
  cout << len << endl;
  return 0;
}

输出结果为5，说明从起点到终点的最短路径长度为5。

通过上述例子，我们可以看出C++中实现深度优先搜索并求得最短路径的方法十分简单，只需要实现状态类以及getnextstate和isendstate两个函数即可。希望本文对大家学习C++深度优先搜索有所帮助。

上一篇: idea打包java可执行jar包

下一篇: 可以卸载Micorosoft Visual C++吗？

评论区

()

相似文章