2401_83026892 2024-02-23 22:15 采纳率: 20%

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

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

/******在栈中加入一个元素******/
{
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;
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;}

``````

```

• 写回答

#### 13条回答默认 最新

• 檀越剑指大厂 Java领域优质创作者 2024-02-23 22:15
关注

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` 变量，并指定起点和终点坐标作为函数参数。如果迷宫中没有通向终点的路径，函数将不会返回任何内容。

评论

#### 问题事件

• 已结题 （查看结题原因） 2月24日
• 修改了问题 2月24日
• 修改了问题 2月23日
• 创建了问题 2月23日

#### 悬赏问题

• ¥15 有没有人会打学生成绩管理系统呀
• ¥15 在使用Fiddler和夜神模拟器抓包的时候一直出现443该怎么办啊QAQ搜了好几个笔记都没有解决
• ¥15 3x7的二维数组A、B、C，A中的任意1个数组元素与B的任意1个数组元素、同时又与C的任意1个数组元素比较，把不同位置出现相同数的比较称为无意义，反之称为有意义，把有意义的比较打印输出。
• ¥20 预测模型怎么处理原始数据（随机森林）
• ¥20 请问discuz3.5如何实现插入ckplayer全能播放器功能呢？
• ¥15 thingsboard代码编译出错误
• ¥15 博途v18仿真报错怎么解决
• ¥15 欧姆龙plc枕式包装机 ST编程
• ¥15 为啥快手广告联盟的广告这么难出来
• ¥15 k8s集群重启后，kubelet一直报systemctl restart kubelet.service "Failed to delete cgroup paths"