C++中采用栈和BFS算法求解迷宫问题

Question

这个在c++中如何打印路径程序大概思路能提供一下吗，写代码如何写通过数组和栈输出迷宫路径求详细解法[](

``#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>
#define N            8
#define MAX_STACK_SIZE        N*N                        /*最大栈容量 */
#define TRUE            1
#define FALSE            0
#define LEN            (300/N)

/******结构体记录每一步的横坐标，纵坐标和方向******/
typedef struct {
    short int row;
    short int col;
    short int dir;
    }element;

element stack[MAX_STACK_SIZE];

/******结构体记录水平和垂直的偏移量******/
typedef struct {
    short int vert;
    short int horiz;
    }offsets;

offsets move[8];                /* 8个方向的move    */

int maze[N+2][N+2];            /*二维数组记录迷宫*/
int mark[N+2][N+2];            /*记录迷宫中每点是否可到达*/
int EXIT_ROW = N, EXIT_COL = N;


/******在栈中加入一个元素******/
void add(int *top, element item)
{
    if (*top >= MAX_STACK_SIZE - 1)
    {
    printf("The stack is full!\n");
    return;
    }
    stack[++*top] = item;
}

/******返回栈中顶部的元素******/
element deleteElement(int *top)
{
    if (*top == -1)
    {
        printf("The stack is empty ! \n");
        exit(1);
    }
    return stack[(*top)--];
}

/******输出走出迷宫的路径******/
void path(void)
{
      int i, j, k, row, col, next_row, next_col, dir, found = FALSE;
     int gd =VGA;
     int gm =VGAHI;

    /*--------------------------------------------------------------*\
    |    i           --->    用来循环计数            |
    |    row , col     --->    当前位置的坐标          |
    |    next_row    --->    移动后的位置的横坐标    |
    |    next_col     --->    移动后的位置的纵坐标    |
    |    dir            --->    移动的方向              |
    |    found        --->    标志路径是否发现        |
    \*--------------------------------------------------------------*/

      element position;
      int top = 0;
      mark[1][1] = 1;                    /* maze[1][1]已经被走过了*/
      stack[0].row = 1;
      stack[0].col = 1;
      stack[0].dir = 1;                    /*第一步的状态*/
      move[0].vert = -1; move[0].horiz = 0 ;
      move[1].vert = -1; move[1].horiz = 1 ;
      move[2].vert = 0 ; move[2].horiz = 1 ;
      move[3].vert = 1 ; move[3].horiz = 1 ;
      move[4].vert = 1 ; move[4].horiz = 0 ;
      move[5].vert = 1 ; move[5].horiz = -1;
      move[6].vert = 0 ; move[6].horiz = -1;
      move[7].vert = -1; move[7].horiz = -1;


      initgraph(&gd,&gm,"");       /* 指定了八个方向*/

      /*---------------------------------------------------------------------------*\
      |     主要算法描述:                                         |
      |            当stack不为空,移动到stack顶部的位置           |
      |     试着向各个方向移动，如果可以移动就移动到        |
|     下一个位置并把它标志成1。                       |
      |     然后保存状态并加入到stack中                        |
      |     如果路径被破坏，或者不存在，就将其删除           |
      |     并返回到上一点继续遍历其他方向的点               |
      |     直到一条路径被发现。                            |
      \*-----------------------------------------------------------------------------*/
      while ( top > -1 && !found) {      /*stack不为空*/

        position = deleteElement(&top);         /*删除stack中的元素*/

        row = position.row;
        col = position.col;
        dir = position.dir;

        while (dir < 8 && !found) {     

          next_row = row + move[dir].vert;
          next_col = col + move[dir].horiz;

          if (next_row == EXIT_ROW && next_col == EXIT_COL)
            found = TRUE;          /*发现路径*/

          else if ( !maze[next_row][next_col] &&
            !mark[next_row][next_col])
                                /*如果这点没有被走过并且可以走*/
          {
            mark[next_row][next_col] = 1;  /*设成1*/
                position.row = row;
            position.col = col;
            position.dir = ++dir;
            add(&top, position);           /*加入到stack*/
            row = next_row;
            col = next_col;
            dir = 0;                      /* 移动到下一个点 */
           }
             else ++dir;                  /*尝试其他方向*/
        }
    }
    for(j=1;j<=N;j++)
       for(k=1;k<=N;k++)
{
          setcolor(WHITE);
          circle(j*LEN,k*LEN,10);
          setcolor(MAGENTA);
          outtextxy(j*LEN-2,k*LEN-2,maze[k][j]?"1":"0");
       }
    if (found)
{                         /* 如果发现路径，则打印出来*/
      outtextxy(20,10,"The path is:");
      setcolor(YELLOW);
      for (i=0; i <top;i++)
{
        line(stack[i].col*LEN, stack[i].row*LEN,stack[i+1].col*LEN,stack[i+1].row*LEN);
      }
      line(stack[i].col*LEN, stack[i].row*LEN,col*LEN,row*LEN);
      line(col*LEN, row*LEN,EXIT_COL*LEN,EXIT_ROW*LEN);
    }
      else outtextxy(20,10,"The maze does not have a path");
                             /* 否则打印不存在信息*/
}

int main()
{
    int i, j, c;
    randomize();
    system("cls");
    for (i=0;i<N+2;i++)
    {
        maze[0][i]=1;
        maze[i][0]=1;
        maze[N+1][i]=1;
        maze[i][N+1]=1;
    }                /* 将迷宫的四周设为1（墙壁） */

    printf("Would you like to input the maze by youself?\nYes or No?");
    c = getchar();
    if(c=='Y' || c== 'y')
    {
        printf("Enter the %d * %d maze:\n",N,N);   /*手动输入*/
        for (i=1; i<N+1; i++)
          for(j=1; j<N+1; j++)
          {
              scanf("%d",&maze[i][j]);             
          }
    }
    else
    {
         printf("The maze is created by the computer:\n");
         for (i=1; i<N+1; i++)
           for(j=1; j<N+1; j++)
          {
              maze[i][j]=random(2);
          }
         maze[N][N] = 0;
         maze[1][1] = 0;
         for(i=1;i<N+1;i++)
         {
           for(j=1;j<N+1;j++)
              printf("%3d",maze[i][j]);
           printf("\n");
         }
    }
    path();                           /* 调用函数path() */
    getch();
    return 0;}
如何修改代码在devc++上运行`，通过其他方式显示路径

Answer 1

参考通义千问和郭老师的小迷弟雅思莫了-编写提供，您可以参考如下，如果回答的不正确，及时评论区回复我，我会根据你错误描述追加回复。如果解决了您的问题，麻烦帮我点击个采纳！谢谢您的肯定！

首先，你的代码中使用了图形库<graphics.h>，这可能在某些编译器（比如Dev-C++）中不可用。如果你希望在控制台环境中运行，并且只关注找到路径而不是可视化路径，你可以去掉这部分代码。

以下是修改后的代码思路：

1. 创建一个新的结构体PathStep来存储当前位置、方向以及到达该位置的父节点。
2. 使用广度优先搜索(BFS)来寻找从起点到终点的路径。在这个过程中，使用一个队列代替栈来存储路径。
3. 在BFS过程中，将每个可达的节点加入队列，并标记为已访问。
4. 每次从队列中取出一个节点，检查它是否是终点。如果是，结束搜索；如果不是，尝试所有可能的方向，并添加未访问过且可通过的邻居节点到队列。
5. 记录每个节点的父节点，这样当找到终点时，可以通过回溯父节点来获取整个路径。
6. 在找到路径后，从终点开始，沿着父节点反向构造路径，然后打印出来。

以下是简化版的代码示例，仅考虑逻辑部分，不包含图形化输出：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 8;
const int directions[] = {0, 1, 1, 1, 0, -1, -1, -1};

struct PathStep {
    int row, col, parent_dir;
};

bool isValidMove(const vector<vector<int>>& maze, int row, int col, int dir) {
    int newRow = row + directions[dir];
    int newCol = col + directions[dir + 1];
    return newRow >= 0 && newRow < N && newCol >= 0 && newCol < N && !maze[newRow][newCol];
}

vector<vector<int>> maze(N, vector<int>(N));
vector<vector<int>> visited(N, vector<int>(N));

pair<int, int> findPath(int startRow, int startCol, int endRow, int endCol) {
    queue<PathStep> q;
    q.push({startRow, startCol, -1});
    visited[startRow][startCol] = 1;

    while (!q.empty()) {
        PathStep current = q.front();
        q.pop();

        if (current.row == endRow && current.col == endCol)
            return {current.parent_dir, true}; // 返回最后一个方向和找到路径

        for (int dir = 0; dir < 8; dir++) {
            int newRow = current.row + directions[dir];
            int newCol = current.col + directions[dir + 1];

            if (isValidMove(maze, newRow, newCol, dir)) {
                q.push({newRow, newCol, dir});
                visited[newRow][newCol] = 1;
            }
        }
    }

    return {-1, false}; // 没有找到路径
}

void printPath(int startRow, int startCol, int endRow, int endCol) {
    vector<pair<int, int>> path;
    int row = endRow, col = endCol, dir;

    while (row != startRow || col != startCol) {
        tie(dir, row, col) = findPath(row, col, row - directions[dir], col - directions[dir + 1]);
        path.push_back({dir, {row, col}});
    }

    cout << "Path: ";
    for (auto& step : path)
        cout << "Right" << step.first << ", ";

    cout << endl;
}

int main() {
    // 初始化迷宫和边界条件
    // ...

    // 找到并打印路径
    pair<int, bool> result = findPath(1, 1, N, N);
    if (result.second)
        printPath(1, 1, N, N);
    else
        cout << "No path exists." << endl;

    return 0;
}

请注意，上述代码需要根据你的实际迷宫数据结构进行调整。这里假设迷宫是一个二维整型数组，其中0表示可通过，1表示墙。此外，你需要自己填充初始化迷宫的部分。