C++编写迷宫求解代码 |21xrx.com

C++编写迷宫求解代码

2023-07-04 22:09:14 深夜i 14 0

C++ 迷宫求解代码

迷宫游戏是一种极具挑战性和趣味性的智力游戏，而编写一个迷宫求解代码则可以更深入的了解其中的算法和原理。在这篇文章中，我们将探讨如何使用C++编写一个简单的迷宫求解代码。

首先，我们需要了解迷宫求解的算法。典型的迷宫求解算法是深度优先搜索（DFS）和广度优先搜索（BFS）。其中，DFS是将每个格子递归地遍历，直到找到出口；BFS则是逐层地遍历迷宫，直到找到出口。

接下来，我们将使用C++来实现DFS算法。我们需要定义一个二维数组来表示迷宫，其中0表示可走的路径，1表示不可走的墙壁。我们还需要定义一个栈来存储未访问过的路径和一个路径向量来保存访问过的路径。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int ROW = 10;
const int COL = 10;
int maze[ROW][COL] = {
   1,
   0,
   1,
  1,
   0,
   0,
  0,
   0,
   0,
   1
};
stack<pair<int, int>> s;
vector<pair<int, int>> pathVector;

接下来，我们需要编写一个函数，该函数将使用迭代的方式来遍历迷宫，并找到从起点到终点的路径。当该函数找到终点时，它将把路径向量返回。

vector<pair<int, int>> findPath(int row, int col, int targetRow, int targetCol) {
  vector<pair<int, int>> res;
  s.push(make_pair(row, col));
  while (!s.empty()) {
    auto top = s.top();
    s.pop();
    if (top.first == targetRow && top.second == targetCol)
      res = pathVector;
      break;
    
    pathVector.push_back(top);
    if (top.second + 1 < COL && maze[top.first][top.second + 1] == 0) {
      s.push(make_pair(top.first, top.second + 1));
      maze[top.first][top.second + 1] = 1;
    }
    if (top.first - 1 >= 0 && maze[top.first - 1][top.second] == 0) {
      s.push(make_pair(top.first - 1, top.second));
      maze[top.first - 1][top.second] = 1;
    }
    if (top.second - 1 >= 0 && maze[top.first][top.second - 1] == 0) {
      s.push(make_pair(top.first, top.second - 1));
      maze[top.first][top.second - 1] = 1;
    }
    if (top.first + 1 < ROW && maze[top.first + 1][top.second] == 0) {
      s.push(make_pair(top.first + 1, top.second));
      maze[top.first + 1][top.second] = 1;
    }
  }
  return res;
}

最后，我们可以在主函数中调用findPath函数，并打印出找到的路径。

int main() {
  auto res = findPath(0, 0, 9, 9);
  for (auto p : res) {
    cout << "(" << p.first << ", " << p.second << ")" << endl;
  }
  return 0;
}

通过本文，我们了解了如何使用C++编写一个简单的迷宫求解代码。尽管这只是一个很小的例子，但它向我们展示了如何使用算法解决问题，并用代码将其实现。我们可以使用这个小例子为我们今后的编程工作打下坚实的基础。

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

下一篇: C++语言中哪个运算符无法被重载？

评论区

相似文章