C++ 栈实现迷宫问题 |21xrx.com

C++ 栈实现迷宫问题

2023-07-04 08:32:51 深夜i -- --

C++ 栈迷宫问题实现数据结构

迷宫问题是一个经典的算法问题，其中需要在给定的迷宫中寻找一条从起点到终点的路径。在这个问题中，我们可以使用栈来实现深度优先搜索算法来解决迷宫问题。

在C++中，我们可以使用vector来实现栈。vector是一个动态数组，它能够自动扩展并收缩。我们可以使用vector的push_back()函数在栈顶添加元素，pop_back()函数删除栈顶元素。

下面是使用C++ vector实现栈的模板代码：


template<class T>
class Stack {
 private:
  vector<T> elements;
 public:
  void push(const T& element);
  void pop();
  T top() const;
  bool empty() const {
    return elements.empty();
  }
};
template<class T>
void Stack<T>::push(const T& element) {
  elements.push_back(element);
}
template<class T>
void Stack<T>::pop() {
  if (elements.empty()) {
    throw out_of_range("Stack<>::pop(): empty stack");
  }
  elements.pop_back();
}
template<class T>
T Stack<T>::top() const {
  if (elements.empty()) {
    throw out_of_range("Stack<>::top(): empty stack");
  }
  return elements.back();
}

接下来，我们需要定义一些迷宫问题中的数据结构。我们可以定义一个结构体来表示每个迷宫格子的状态：


struct Cell
  int x;
  int y;
  bool visited;
  bool wallUp;
  bool wallRight;
  bool wallDown;
  bool wallLeft;
;

在这个结构体中，x和y表示格子的坐标，visited表示该格子是否已经被访问，wallUp，wallRight，wallDown和wallLeft分别表示该格子上、右、下和左四个方向是否有障碍物。

接下来，我们可以实现一个函数来检查给定的格子是否是可访问的。如果格子超出了迷宫边界，或者已经被访问过，或者存在障碍物，那么它是不可访问的。


bool isAccessible(const Cell& cell, const vector<vector<Cell>>& maze) {
  int rows = maze.size();
  int columns = maze[0].size();
  if (cell.x < 0 || cell.x >= rows || cell.y < 0 || cell.y >= columns)
    return false;
  
  if (maze[cell.x][cell.y].visited || maze[cell.x][cell.y].wallUp || maze[cell.x][cell.y].wallRight || maze[cell.x][cell.y].wallDown || maze[cell.x][cell.y].wallLeft)
    return false;
  
  return true;
}

现在，我们可以实现迷宫问题的解决算法。我们从起点开始，把它入栈。接下来，我们不断从栈顶弹出元素，并查找它周围的可访问格子。对于每个可访问的格子，我们将其标记为已访问，并入栈。如果我们找到了终点，那么我们可以返回路径。如果栈为空，那么我们可以认为没有路径。


vector<Cell> findPath(vector<vector<Cell>>& maze, const Cell& start, const Cell& end) {
  Stack<Cell> stack;
  stack.push(start);
  maze[start.x][start.y].visited = true;
  while (!stack.empty()) {
    Cell currentCell = stack.top();
    if (currentCell.x == end.x && currentCell.y == end.y) {
      vector<Cell> path;
      while (!stack.empty()) {
        path.push_back(stack.top());
        stack.pop();
      }
      return path;
    }
    bool foundAccessibleCell = false;
    // Check up
    Cell nextCell(currentCell.x - 1, currentCell.y);
    if (isAccessible(nextCell, maze)) {
      stack.push(nextCell);
      foundAccessibleCell = true;
    }
    // Check right
    nextCell.x = currentCell.x;
    nextCell.y = currentCell.y + 1;
    if (isAccessible(nextCell, maze)) {
      stack.push(nextCell);
      foundAccessibleCell = true;
    }
    // Check down
    nextCell.x = currentCell.x + 1;
    nextCell.y = currentCell.y;
    if (isAccessible(nextCell, maze)) {
      stack.push(nextCell);
      foundAccessibleCell = true;
    }
    // Check left
    nextCell.x = currentCell.x;
    nextCell.y = currentCell.y - 1;
    if (isAccessible(nextCell, maze)) {
      stack.push(nextCell);
      foundAccessibleCell = true;
    }
    if (!foundAccessibleCell) {
      stack.pop();
    }
  }
  return vector<Cell>();
}

最后，我们可以在主函数中使用上述函数来解决给定的迷宫问题。


int main() {
  vector<vector<Cell>> maze = {
    { false, false , false, 3, true },
    { false, 1, false, true, false },
    { true, false, false, true, 4 },
    { 0, true , 3, 3, 4 },
    { true, false, 2, 4, false }
  };
  Cell start(0, 0);
  Cell end(4, 4);
  vector<Cell> path = findPath(maze, start, end);
  if (path.empty())
    cout << "No path found" << endl;
   else {
    cout << "Path found: " << endl;
    for (auto& cell : path) {
      cout << "(" << cell.x << ", " << cell.y << ")" << endl;
    }
  }
  return 0;
}

使用以上代码，我们可以成功地找到迷宫中的路径。通过使用C++中的栈和深度优先搜索算法，我们可以轻松地解决迷宫问题。

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

下一篇: 如何在C++中生成随机数？

评论区

()

相似文章