采用栈和深度优先算法取消graphics库采用其他方式显示路径打印显示路径取消graphics库

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;}

```

Answer 1

2401_83026892 晚上好🌙🌙🌙
本答案参考通义千问

要对你的代码进行修改以实现迷宫问题的解决（使用栈和深度优先搜索算法），首先，我们需要明确迷宫数据结构的表示以及当前的状态追踪。一个常见的迷宫数据结构可以是二维数组，其中0代表通路，1代表墙壁。深度优先搜索（DFS）的基本思想是从起点开始，尽可能深地搜索迷宫，直到找到终点或无法继续为止。

迷宫数据结构示例：

maze = [
    [0, 0, 0, 1, 0], 
    [0, 1, 0, 1, 0], 
    [0, 0, 0, 0, 0], 
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0]
]

接下来，我们将实现深度优先搜索的栈辅助方法，并返回从起点到终点的路径：

from collections import deque

def dfs(maze, start=(0, 0), end=(len(maze) - 1, len(maze[0]) - 1)):
    stack = [(start, [start])]
    
    while stack:
        current_pos, path = stack.pop()
        
        if current_pos == end:
            return path
        
        x, y = current_pos
        
        # 检查当前位置上下左右四个方向是否为通路且未访问过
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]) and maze[next_x][next_y] == 0 and (next_x, next_y) not in path:
                stack.append(((next_x, next_y), path.copy() + [next_x, next_y]))

# 示例调用
path = dfs(maze)
print("Path from start to end:", path)

这段代码将输出从起点 (0, 0) 到终点 (4, 3) 的路径。请注意，你需要根据实际迷宫数据结构调整 maze 变量，并指定起点和终点坐标作为函数参数。如果迷宫中没有通向终点的路径，函数将不会返回任何内容。