C++代码：老鼠走迷宫 |21xrx.com

C++代码：老鼠走迷宫

2023-07-05 22:40:52 深夜i -- --

C++代码老鼠走迷宫迷宫求解搜索算法递归函数

在计算机编程领域，C++语言被广泛应用于游戏开发、图形处理和科学计算。在C++语言中，有各种有趣的编程题目供程序员挑战。

其中一个经典的编程题目就是“老鼠走迷宫”。这个问题是在一个迷宫中找到一条从起点到终点的最短路径。一般来说，迷宫由一些障碍物和通行区域组成。老鼠只能沿着通行区域移动，不能穿过障碍物。

为了解决这个问题，我们可以利用C++语言的图论算法来实现。具体来说，我们可以采用广度优先搜索算法（BFS），它可以从起点一步一步地扩展搜索范围，直到找到到达目标节点的路径为止。

以下是一个C++代码示例，用于解决“老鼠走迷宫”问题：


#include <iostream>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int dx[4] = 0;
const int dy[4] = 1;
int N, M;      // 迷宫的行数和列数
char maze[MAX_N][MAX_N]; // 迷宫的地图
int sx, sy;     // 起点的坐标
int gx, gy;     // 终点的坐标
int d[MAX_N][MAX_N];   // 从起点到各个位置的最短距离
bool ok[MAX_N][MAX_N];  // 是否已经搜索过
struct Node y;
;
void bfs() {
  queue<Node> q;
  q.push(Node sy);
  d[sx][sy] = 0;
  ok[sx][sy] = true;
  while (!q.empty()) {
    Node node = q.front();
    q.pop();
    if (node.x == gx && node.y == gy)
      break;
    
    for (int i = 0; i < 4; i++) {
      int nx = node.x + dx[i];
      int ny = node.y + dy[i];
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#' && !ok[nx][ny]) {
        q.push(Node ny);
        ok[nx][ny] = true;
        d[nx][ny] = d[node.x][node.y] + 1;
      }
    }
  }
}
int main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> maze[i][j];
      if (maze[i][j] == 'S')
        sx = i;
        sy = j;
       else if (maze[i][j] == 'G')
        gx = i;
        gy = j;
      
    }
  }
  bfs();
  cout << d[gx][gy] << endl;
  return 0;
}

上述代码首先输入了一个字符型的迷宫地图，并且找到了起点和终点的坐标。然后，它使用BFS算法来搜索从起点到终点的最短路径，并输出了结果。使用此代码，程序员可以轻松地实现“老鼠走迷宫”问题。

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

下一篇: C++多维数组输入方法详解

评论区

()

相似文章