【实验三】栈及其应用——迷宫问题

标签：Node temp 迷宫 next 实验 应用 Now Stack

第一部分  实验要求

【问题描述】 以一个 m × n 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序；求得的通路以三元组(i ， j ， d) 的形式输出，其中： (i ， j) 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1 , 1 , 1) , (1 , 2 , 2) , (2 ,2, 2) , (3 , 2 , 3) , (3 , 1 , 2) ，… 【测试数据】 迷宫的测试数据如下：左上角 (1 ， 1) 为入口右下角 (9 ， 8) 为出口。 【实现提示】 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探 索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置， 求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 【选作内容】 (1) 以方阵形式输出迷宫及其通路。

第二部分  实现代码

以下给出两份实现代码，两份代码均由C++编写。其中第一份代码使用了深度优先搜索策略并实现和使用了栈这一数据结构，第二份代码使用了广度优先搜索策略。实验报告的主体部分围绕第一份实验代码给出，在实验报告的第7节对第二份代码进行了简要说明。

实现代码1

#include<iostream>
#define Past_Dream FW
using namespace std;
#define Max 998244353
struct Stack_Node{
    int x , y , op;
    Stack_Node *next;
    Stack_Node(int _x=0,int _y=0){
        x=_x;
        y=_y;
        op = 0;
        next=NULL;
    }
};
class My_Stack{
    Stack_Node *top;
public:
    void Stack_Init();
    void Stack_Push(Stack_Node *p);
    Stack_Node* Stack_Pop();
    Stack_Node* Stack_Top();
    bool Stack_Empty();
    void Stack_Clear();
    void Stack_Destroy();
};
void My_Stack::Stack_Init(){
    top=NULL;
}
void My_Stack::Stack_Push(Stack_Node *p){
    p->next=top;
    top=p;
}
Stack_Node* My_Stack::Stack_Pop(){
    Stack_Node *p=top;
    top=top->next;
    return p;
}
Stack_Node* My_Stack::Stack_Top(){
    return top;
}
bool My_Stack::Stack_Empty(){
    return (top==NULL);
}
void My_Stack::Stack_Clear(){
    while(top!=NULL){
        Stack_Pop();
    }
}
void My_Stack::Stack_Destroy(){
    while(top!=NULL){
        Stack_Node *p=top;
        top=top->next;
        delete p;
    }
}
Stack_Node *nil = new Stack_Node(0,0);
Stack_Node* Next_Node_op(Stack_Node *p, Stack_Node *Now, Stack_Node *Dead){
    Stack_Node *next = new Stack_Node(Now->x, Now->y);
    if(Dead == nil){
        if(p == nil){
            next->x = Now->x - 1;
            next->y = Now->y;
            return next;
        }
        if(Now->x == p->x+1 && Now->y == p->y){
            next->x = Now->x;
            next->y = Now->y+1;
            Now->op = 1;
            return next;
        }
        else if(Now->x == p->x-1 && Now->y == p->y){
            next->x = Now->x;
            next->y = Now->y-1;
            Now->op = 3;
            return next;
        }
        else if(Now->x == p->x && Now->y == p->y+1){
            next->x = Now->x-1;
            next->y = Now->y;
            Now->op = 4;
            return next;
        }
        else if(Now->x == p->x && Now->y == p->y-1){
            next->x = Now->x+1;
            next->y = Now->y;
            Now->op = 2;
            return next;
        }
    }else{
        if(Dead->x == Now->x+1 && Dead->y == Now->y){
            next->x = Now->x;
            next->y = Now->y-1;
            Now->op = 3;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
        else if(Dead->x == Now->x-1 && Dead->y == Now->y){
            next->x = Now->x;
            next->y = Now->y+1;
            Now->op = 1;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
        else if(Dead->x == Now->x && Dead->y == Now->y+1){
            next->x = Now->x+1;
            next->y = Now->y;
            Now->op = 2;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
        else if(Dead->x == Now->x && Dead->y == Now->y-1){
            next->x = Now->x-1;
            next->y = Now->y;
            Now->op = 4;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
    }
    return nil;
}
int main(){
    int n , m, start_x, start_y, end_x, end_y;
    cout << "Please enter the number of rows and columns of the maze:";
    cin >> n >> m ;
    int a[n+1][m+1];
    char g_ans[n+1][m+1];
    cout << "Please enter the maze layout (0 means passable, 1 means obstacle):" << endl;
    for(int i = 1 ;i <= n ; i++ ){
        for(int j = 1 ; j <= m ; j++ ){
            cin >> a[i][j];
            g_ans[i][j] = a[i][j] +48 ;
        }
    }
    cout << "Please enter the starting and ending coordinates (x y):" << endl;
    cin >> start_x >> start_y >> end_x >> end_y;
    cout << "------------------Ans------------------" << endl;
    if(a[start_x][start_y] == 1 || a[end_x][end_y] == 1 || start_x > n || start_x < 1 || start_y > m || start_y < 1 || end_x > n || end_x < 1 || end_y > m || end_y < 1){
        cout << "No" << endl;
        cout << "---------------------------------------" << endl;
        return 0;
    }
    My_Stack s , ans;
    s.Stack_Init();
    ans.Stack_Init();
    Stack_Node *p = new Stack_Node(start_x-1, start_y);
    Stack_Node *Now = new Stack_Node(start_x, start_y);
    Stack_Node *Dead = nil;
    Stack_Node *next = nil;
    Stack_Node *temp_p_Start = p;
    p=nil;
    s.Stack_Push(Now);
    while(!s.Stack_Empty()){
        Now = (s.Stack_Top());
        if(Now->x == end_x && Now->y == end_y){
            cout << "Yes" << endl;
            cout << "---------------------------------------" << endl;
            break;
        }
        next = Next_Node_op(p, Now, Dead);
        if(next == nil){
            Dead = s.Stack_Pop();
            if(!s.Stack_Empty())Now = s.Stack_Pop();
            else break;
            if(!s.Stack_Empty())p = s.Stack_Top();
            else p = temp_p_Start;
            s.Stack_Push(Now);   
        }else{
            if(a[next->x][next->y] == 0 && next->x > 0 && next->x < n+1 && next->y > 0 && next->y < m+1 && (next->x != p->x || next->y != p->y)){
                p = Now;
                s.Stack_Push(next);
                Now = next;
                Dead = nil;
            }else{
                Dead = next;
            }
        }
    }
    if(s.Stack_Empty()){
        cout << "No" << endl;
        cout << "---------------------------------------" << endl;
    }else{
        Stack_Node *temp ;
        while(!s.Stack_Empty()){        
            temp = s.Stack_Pop();
            ans.Stack_Push(temp);
            /*
            if((temp->op & 0x1 && g_ans[temp->x][temp->y] == 124) || ((!temp->op & 0x1) && g_ans[temp->x][temp->y] == 95)) g_ans[temp->x][temp->y] = 43;
            else if(temp->op & 0x1) g_ans[temp->x][temp->y] = 95;
            else g_ans[temp->x][temp->y] = 124;
            */
            g_ans[temp->x][temp->y] = 43;
        }
        while(!ans.Stack_Empty()){
            Stack_Node t = *(ans.Stack_Top());
            cout << "(" << t.x << ", " << t.y << ", " << t.op << ")";
            ans.Stack_Pop();
        }
        cout << endl;
        cout << "---------------------------------------" << endl;
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){
                cout << g_ans[i][j] << " ";
            }
            cout << endl;
        }
        cout << "---------------------------------------" << endl;
    }
    s.Stack_Destroy();
    ans.Stack_Destroy();
    return 0;
}

实现代码2

#include<iostream>
#define Past_Dream FW
using namespace std;
#define Max 998244353
int main()
{
    int m , n , p_temp , p_t_temp , dtemp;
    cout << "Please enter the number of rows and columns of the maze:";
    cin >> m >> n;
    int a[m+2][n+2],d[m+2][n+2][2],temp[m*n][2],t_temp[m*n][2];
    cout << "Please enter the maze layout (0 means passable, 1 means obstacle):" << endl;
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            cin >> a[i][j];
            d[i][j][0] = Max;
            d[i][j][1] = 0;
        }
    }
    int x1 , y1 , x2 , y2;
    cout << "Please enter the starting and ending coordinates (x y):" << endl;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << "------------------Ans------------------" << endl;
    p_temp = 1;
    temp[1][0] = x1 , temp[1][1] = y1;
    d[x1][y1][0] = 0; 
    if(a[x2][y2] == 1){
        cout << "No" << endl;
        return 0;
    }
    while(p_temp != 0 && d[x2][y2][0] >= Max){
        p_t_temp = 1;
        for(int i = 1 ; i <= p_temp ; i++){
            if(temp[i][0] != 1 && a[temp[i][0]-1][temp[i][1]]!=1){
                dtemp = d[temp[i][0]][temp[i][1]][0] + 1;
                if(dtemp < d[temp[i][0]-1][temp[i][1]][0]){
                    d[temp[i][0]-1][temp[i][1]][0] = dtemp;
                    d[temp[i][0]-1][temp[i][1]][1] = 4;
                    t_temp[p_t_temp][0] = temp[i][0]-1;
                    t_temp[p_t_temp][1] = temp[i][1];
                    p_t_temp++;
                }
            }
            if(temp[i][0] != m && a[temp[i][0]+1][temp[i][1]]!=1){
                dtemp = d[temp[i][0]][temp[i][1]][0] + 1;
                if(dtemp < d[temp[i][0]+1][temp[i][1]][0]){
                    d[temp[i][0]+1][temp[i][1]][0] = dtemp;
                    d[temp[i][0]+1][temp[i][1]][1] = 2;
                    t_temp[p_t_temp][0] = temp[i][0]+1;
                    t_temp[p_t_temp][1] = temp[i][1];
                    p_t_temp++;
                }
            }
            if(temp[i][1] != 1 && a[temp[i][0]][temp[i][1]-1]!=1){
                dtemp = d[temp[i][0]][temp[i][1]][0] + 1;
                if(dtemp < d[temp[i][0]][temp[i][1]-1][0]){
                    d[temp[i][0]][temp[i][1]-1][0] = dtemp;
                    d[temp[i][0]][temp[i][1]-1][1] = 3;
                    t_temp[p_t_temp][0] = temp[i][0];
                    t_temp[p_t_temp][1] = temp[i][1]-1;
                    p_t_temp++;
                }
            }
            if(temp[i][1] != n && a[temp[i][0]][temp[i][1]+1]!=1){
                dtemp = d[temp[i][0]][temp[i][1]][0] + 1;
                if(dtemp < d[temp[i][0]][temp[i][1]+1][0]){
                    d[temp[i][0]][temp[i][1]+1][0] = dtemp;
                    d[temp[i][0]][temp[i][1]+1][1] = 1;
                    t_temp[p_t_temp][0] = temp[i][0];
                    t_temp[p_t_temp][1] = temp[i][1]+1;
                    p_t_temp++;
                }
            }
        }
        p_temp = p_t_temp - 1;
        for(int i = 1 ; i <= p_temp ; i++){
            temp[i][0] = t_temp[i][0];
            temp[i][1] = t_temp[i][1];
        }
    }
    if(d[x2][y2][0] == Max){
        cout << "No" << endl;
        cout << "---------------------------------------" << endl;
    }else{
        cout << "Yes" << endl;
        cout << "---------------------------------------" << endl;
        for(int i = 1 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                if(d[i][j][0] == Max){
                    cout << "- ";
                }
                else cout << d[i][j][0] << " ";
            }
            cout << endl;
        }
        cout << "---------------------------------------" << endl;
        int x = x2 , y = y2;
        p_temp = 1;
        temp[p_temp][0] = x;
        temp[p_temp][1] = y;
        temp[0][0] = 0;
        temp[0][1] = 0;
        a[x][y] = 8;
        p_temp++;
        while(x!=x1 || y!=y1){
            switch(d[x][y][1]){
                case 1:
                    y--;
                    break;
                case 2:
                    x--;
                    break;
                case 3:
                    y++;
                    break;
                case 4:
                    x++;
                    break;
                default:
                    break;    
            }
            temp[p_temp][0] = x;
            temp[p_temp][1] = y;
            a[x][y] = 8;
            p_temp ++;
        }
        d[0][0][1] = 0;
        cout << "The shortest path is:" << endl;
        for(int i = p_temp-1 ; i >= 1 ; i--){
            cout << "(" << temp[i][0] << ", " << temp[i][1] << " ," << d[temp[i-1][0]][temp[i-1][1]][1] << ")" ;
        }
        cout << endl;
        cout << "The length of the shortest path is: " << d[x2][y2][0] << endl;
        cout << "---------------------------------------" << endl;
        for(int i = 1 ; i <= m ; i++){
            for(int j = 1 ; j <= n ; j++){
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
        cout << "---------------------------------------" << endl;
    }
    return 0;
}

第三部分  实验报告

一、需求分析

本程序的主要任务是实现迷宫问题的求解。以一个 m×n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍，对任意设定的迷宫，程序需要求出一条从入口到出口的通路，或得出没有通路的结论。

输入：

第一行输入迷宫的行数m与列数n

接下来m行的0/1序列，每行有n个0或1，表示迷宫对应位置(i,j)是否可以通行（0表示通行，1表示障碍）

接下来输入起始点的坐标(start_x,start_y)，终点的坐标(end_x,end_y)

输出：

首先输出一行结论Yes/No，表示是否存在一条从入口到出口的通路

如果结论为Yes，以三元组(i，j，d)的形式输出通路，其中：(i，j)指示迷宫中的一个坐标，d 表示走到下一坐标的方向。

【坐标与方向约定】

我们建系如下图所示，二元组(i,j)表示坐标，i表示x坐标，j表示y坐标

关于方向，我们约定向y+方向为1，向x+方向为2，向y-方向为3，向x-方向为4

测试数据：

9 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
1 1 9 8

二、概要设计

实现上述程序功能，我们使用链表来表示迷宫中的节点及其探索路径。为此定义一个抽象数据类型 My_Stack 来管理这些节点，并提供一系列基本操作。以下是详细的ADT定义：

1.Stack_Init(&s)

初始条件: 无

操作结果: 构造一个空的栈 s。

2.Stack_Push(&s, p)

初始条件: 栈 s 已经存在，且 p 是待入栈的节点指针。

操作结果: 将新节点 p 压入栈顶。

3.Stack_Pop(&s)

初始条件: 栈 s 已经存在。

操作结果: 移除并返回栈顶节点指针。

4.Stack_Top(s)

初始条件: 栈 s 已经存在。

操作结果: 返回栈顶节点指针但不移除它。

5.Stack_Empty(s)

初始条件: 栈 s 已经存在。

操作结果: 若 s 为空，则返回 TRUE，否则返回 FALSE。

6.Stack_Clear(&s)

初始条件: 栈 s 已经存在。

操作结果: 清空栈 s 的内容。

7.Stack_Destroy(&s)

初始条件: 栈 s 已经存在。

操作结果: 销毁栈 s，释放所有节点占用的内存。

数据结构定义

class My_Stack{
    Stack_Node *top;
public:
    void Stack_Init();
    void Stack_Push(Stack_Node *p);
    Stack_Node* Stack_Pop();
    Stack_Node* Stack_Top();
    bool Stack_Empty();
    void Stack_Clear();
    void Stack_Destroy();
};

本程序包含三个主要模块：

1. 主程序模块：

负责初始化系统，接受用户输入的迷宫大小及布局信息，以及起点和终点坐标。

初始化迷宫数组 a 和路径标记数组 g_ans。

创建两个栈 s 和 ans 用于存储搜索过程中的节点和最终找到的路径。

使用深度优先搜索（DFS）算法探索迷宫，尝试从起点到达终点。

如果找到路径，则输出"Yes"并打印路径；如果没有找到路径，则输出"No"。

2.栈的单元模块：

实现了栈的抽象数据类型（ADT），提供了对栈的基本操作如初始化、入栈、出栈等。

支持深度优先搜索算法所需的回溯机制。

3.节点结构的单元模块：

定义了用于表示迷宫位置和移动方向的结构体 Stack_Node。

结构体成员包括当前位置坐标(x, y)、移动方向(op)以及指向下一个节点的指针(next)。

各模块之间的调用关系如下：

三、详细设计

1.结点结构的详细定义(Stack_Node 结构体)：

包含成员变量 x, y 表示结点在迷宫中的坐标。

包含成员变量 op 表示移动方向。

包含成员变量 next 指向栈中下一个结点的指针。

提供构造函数初始化节点，默认方向 op 为 0，next 为 NULL。

struct Stack_Node{
    int x , y , op;
    Stack_Node *next;
    Stack_Node(int _x=0,int _y=0){
        x=_x;
        y=_y;
        op = 0;
        next=NULL;
    }
};

2.栈的单元模块的详细定义 (My_Stack 类):

class My_Stack{
    Stack_Node *top;
public:
    void Stack_Init();
    void Stack_Push(Stack_Node *p);
    Stack_Node* Stack_Pop();
    Stack_Node* Stack_Top();
    bool Stack_Empty();
    void Stack_Clear();
    void Stack_Destroy();
};
void My_Stack::Stack_Init(){
    top=NULL;
}
void My_Stack::Stack_Push(Stack_Node *p){
    p->next=top;
    top=p;
}
Stack_Node* My_Stack::Stack_Pop(){
    Stack_Node *p=top;
    top=top->next;
    return p;
}
Stack_Node* My_Stack::Stack_Top(){
    return top;
}
bool My_Stack::Stack_Empty(){
    return (top==NULL);
}
void My_Stack::Stack_Clear(){
    while(top!=NULL){
        Stack_Pop();
    }
}
void My_Stack::Stack_Destroy(){
    while(top!=NULL){
        Stack_Node *p=top;
        top=top->next;
        delete p;
    }
}

3.哨兵结点（nil）

Stack_Node *nil = new Stack_Node(0,0);

4.主程序模块

main 函数

读取用户输入的迷宫大小 (n, m) 以及迷宫布局。

读取起点和终点坐标。

初始化迷宫数组 a 和路径标记数组 g_ans。

创建两个栈 s 和 ans 并初始化。

将起点位置压入栈 s 开始搜索。

使用 while 循环进行深度优先搜索，直到找到终点或所有可能路径都已尝试。

如果找到路径，将路径节点依次压入栈 ans 并输出路径。

输出路径标记数组 g_ans 显示路径。

int main(){
    int n , m, start_x, start_y, end_x, end_y;
    cout << "Please enter the number of rows and columns of the maze:";
    cin >> n >> m ;
    int a[n+1][m+1];
    char g_ans[n+1][m+1];
    cout << "Please enter the maze layout (0 means passable, 1 means obstacle):" << endl;
    for(int i = 1 ;i <= n ; i++ ){
        for(int j = 1 ; j <= m ; j++ ){
            cin >> a[i][j];
            g_ans[i][j] = a[i][j] +48 ;
        }
    }
    cout << "Please enter the starting and ending coordinates (x y):" << endl;
    cin >> start_x >> start_y >> end_x >> end_y;
    cout << "------------------Ans------------------" << endl;
    if(a[start_x][start_y] == 1 || a[end_x][end_y] == 1 || start_x > n || start_x < 1 || start_y > m || start_y < 1 || end_x > n || end_x < 1 || end_y > m || end_y < 1){
        cout << "No" << endl;
        cout << "---------------------------------------" << endl;
        return 0;
    }
    My_Stack s , ans;
    s.Stack_Init();
    ans.Stack_Init();
    Stack_Node *p = new Stack_Node(start_x-1, start_y);
    Stack_Node *Now = new Stack_Node(start_x, start_y);
    Stack_Node *Dead = nil;
    Stack_Node *next = nil;
    Stack_Node *temp_p_Start = p;
    p=nil;
    s.Stack_Push(Now);
    while(!s.Stack_Empty()){
        Now = (s.Stack_Top());
        if(Now->x == end_x && Now->y == end_y){
            cout << "Yes" << endl;
            cout << "---------------------------------------" << endl;
            break;
        }
        next = Next_Node_op(p, Now, Dead);
        if(next == nil){
            Dead = s.Stack_Pop();
            if(!s.Stack_Empty())Now = s.Stack_Pop();
            else break;
            if(!s.Stack_Empty())p = s.Stack_Top();
            else p = temp_p_Start;
            s.Stack_Push(Now);   
        }else{
            if(a[next->x][next->y] == 0 && next->x > 0 && next->x < n+1 && next->y > 0 && next->y < m+1 && (next->x != p->x || next->y != p->y)){
                p = Now;
                s.Stack_Push(next);
                Now = next;
                Dead = nil;
            }else{
                Dead = next;
            }
        }
    }
    if(s.Stack_Empty()){
        cout << "No" << endl;
        cout << "---------------------------------------" << endl;
    }else{
        Stack_Node *temp ;
        while(!s.Stack_Empty()){        
            temp = s.Stack_Pop();
            ans.Stack_Push(temp);
            /*
            if((temp->op & 0x1 && g_ans[temp->x][temp->y] == 124) || ((!temp->op & 0x1) && g_ans[temp->x][temp->y] == 95)) g_ans[temp->x][temp->y] = 43;
            else if(temp->op & 0x1) g_ans[temp->x][temp->y] = 95;
            else g_ans[temp->x][temp->y] = 124;
            */
            g_ans[temp->x][temp->y] = 43;
        }
        while(!ans.Stack_Empty()){
            Stack_Node t = *(ans.Stack_Top());
            cout << "(" << t.x << ", " << t.y << ", " << t.op << ")";
            ans.Stack_Pop();
        }
        cout << endl;
        cout << "---------------------------------------" << endl;
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){
                cout << g_ans[i][j] << " ";
            }
            cout << endl;
        }
        cout << "---------------------------------------" << endl;
    }
    s.Stack_Destroy();
    ans.Stack_Destroy();
    return 0;
}

辅助函数 Next_Node_op

根据当前节点 Now、前一节点 p 以及不可行节点 Dead 信息计算下一个可行移动位置。根据不同情况更新 Now 的移动方向 op。（计算方式示意图如下）

如果没有可行的移动位置，返回 nil。

Stack_Node* Next_Node_op(Stack_Node *p, Stack_Node *Now, Stack_Node *Dead){
    Stack_Node *next = new Stack_Node(Now->x, Now->y);
    if(Dead == nil){
        if(p == nil){
            next->x = Now->x - 1;
            next->y = Now->y;
            return next;
        }
        if(Now->x == p->x+1 && Now->y == p->y){
            next->x = Now->x;
            next->y = Now->y+1;
            Now->op = 1;
            return next;
        }
        else if(Now->x == p->x-1 && Now->y == p->y){
            next->x = Now->x;
            next->y = Now->y-1;
            Now->op = 3;
            return next;
        }
        else if(Now->x == p->x && Now->y == p->y+1){
            next->x = Now->x-1;
            next->y = Now->y;
            Now->op = 4;
            return next;
        }
        else if(Now->x == p->x && Now->y == p->y-1){
            next->x = Now->x+1;
            next->y = Now->y;
            Now->op = 2;
            return next;
        }
    }else{
        if(Dead->x == Now->x+1 && Dead->y == Now->y){
            next->x = Now->x;
            next->y = Now->y-1;
            Now->op = 3;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
        else if(Dead->x == Now->x-1 && Dead->y == Now->y){
            next->x = Now->x;
            next->y = Now->y+1;
            Now->op = 1;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
        else if(Dead->x == Now->x && Dead->y == Now->y+1){
            next->x = Now->x+1;
            next->y = Now->y;
            Now->op = 2;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
        else if(Dead->x == Now->x && Dead->y == Now->y-1){
            next->x = Now->x-1;
            next->y = Now->y;
            Now->op = 4;
            if(next->x != p->x || next->y != p->y) return next;
            else return nil;
        }
    }
    return nil;
}

5.函数的调用关系图

四、调试分析

1、算法的时空分析

由于采用栈，各种操作的算法时间复杂度基本合理。但是仍可以进一步改善（降低常数项等），在第七部分给出了另一种基于二维数组与类似于单源最短路径问题的Dijkstra 算法的实现。

时间复杂度分析

初始化操作 (InitializeMaze, InitializeStacks, InitializeNodes)

读取迷宫信息 (ReadMazeInfo):

读取迷宫大小 n 和 m，时间复杂度为 O(1)。

读取迷宫布局 a，时间复杂度为 O(n * m)，因为需要遍历整个迷宫。

读取起点和终点坐标，时间复杂度为 O(1)。

初始化栈 (InitializeStacks):

初始化两个空栈 s 和 ans，时间复杂度为 O(1)。

初始化节点 (InitializeNodes):

初始化一些节点指针，时间复杂度为 O(1)。

搜索路径 (SearchPath)

主循环 (while (!s.Stack_Empty())):

每次循环进行了有限次判断，修改了有限个变量，时间复杂度为O(1)。

在最坏情况下，每个节点可能被访问多次（由于回溯），因此总的时间复杂度为 O(n * m)。在极端情况下，如果迷宫中的每个位置都被访问过，那么时间复杂度接近于 O(n * m)。

提取并打印路径 (ExtractAndPrintPath)

从栈 s 中提取路径并将节点压入栈 ans，从栈 ans 中打印路径，最坏情况下时间复杂度为 O(n * m)。

标记并打印迷宫 (MarkAndPrintMaze)

标记路径并打印迷宫，时间复杂度为 O(n * m)。

销毁栈 (DestroyStacks)

销毁栈 s 和 ans，释放所有节点占用的内存。

综上所述，程序的主要部分是搜索路径，整个程序的时间复杂度可以认为是 O(n * m)。

空间复杂度分析

存储结构:

迷宫数组 a 和路径标记数组 g_ans:

每个数组占用的空间为 n * m，空间复杂度为 O(n * m)。

结点结构 Stack_Node:

每个节点包含三个整型变量和一个指针，空间复杂度为 O(1)。

在最坏情况下，可能会创建 n * m 个节点，因此总的空间复杂度为 O(n * m)。

栈 s 和 ans:

每个栈最多会存储 n * m 个节点，因此总的空间复杂度为 O(n * m)。

综上所述，该程序的空间复杂度主要由迷宫数组、路径标记数组、节点结构和栈占用的空间决定，总的空间复杂度为 O(n * m)。

2、小结

实验使用栈实现，调试基本顺利，本人确实得到了一次很好的程序设计训练。

五、用户手册

1、使用环境

操作系统：Windows, macOS, Linux

编译器：支持 C++11 或更高版本的标准编译器（如 GCC, Clang, MSVC）

输入设备：键盘

输出设备：显示器

2、使用说明

2.1 启动程序

确保你的开发环境已经安装了兼容的C++编译器。编译程序并运行编译后的程序。

2.2 输入初始信息

程序启动后，会提示用户输入以下信息：

迷宫大小：程序首先会提示你输入两个整数，分别表示迷宫的行数和列数。

迷宫布局：接下来，程序会要求你输入迷宫的具体布局。每一行代表迷宫的一行，每个数字代表一个单元格的状态（0 表示可以通过，1 表示障碍物）。

起点和终点坐标：最后，程序会要求你输入起点和终点的坐标。坐标从 1 开始计数。

2.3 查看结果

当所有初始信息输入完毕后，程序将开始搜索从起点到终点的路径。

2.3.1 成功找到路径：如果程序找到了从起点到终点的路径，它会输出 "Yes" 并显示路径上的节点坐标及其移动方向。

2.3.2 未找到路径：如果程序未能找到从起点到终点的路径，它会输出 "No"。

六、测试结果

根据测试数据输入后，得到的结果如图（首先输出了结论；第二部分按照实验手册要求输出了一条路径；第三部分使用字符+以方阵形式输出迷宫及其通路）：

七、一种其他实现方式其注释

（源代码如第二部分实现代码2所示，略）

注释

本方法使用了数组a记录迷宫情形，使用了数组d记录了迷宫中各个点与a间的（最近）距离。形象化地，可以理解成先初始化，把起点标记为零，其他地方的距离d均取无穷大（实现上用了一个很大的数MAX）然后在零时刻向起点放了一格子水，每次循环迭代，水都会往边上所有能扩展到的地方扩散一格，直到达到终点，或者没有格子还能被水填充到。循环迭代使用了temp和t_temp数组实现，这两个数组分别记载了上一次循环迭代时水的“边界”与本次循环时水的“边界”。每一次循环时都从上次记录的

与实验正式提交代码的联系与区别

两种方法均为对从起点到终点的搜索。实验正式提交的代码根据课程PPT实现，采用的是深度优先搜索策略；本实现代码采用的是广度优先搜索策略。同时，本实验代码可以找到从起点到终点的一条最短通路。

与单源最短路径问题的Dijkstra 算法的联系与区别

单源最短路径问题是一个经典的算法问题，它的目标是在给定的图中找到从源节点到所有其他节点的最短路径。路径通常由图的边组成，每条边都有一个关联的权重，表示通过该边行走的距离或代价。Dijkstra 算法是解决此问题的一个经典的贪心策略实现，其伪代码及算法正确性证明概要如下。

在迷宫问题中我们可以将迷宫视为一个特殊的图，图中每个点最多与周围4个点有一条权重为1的边。而且一个点被遍历后（将MAX修改为一个其他的值后），再次被遍历时，其值不减（对应Dijkstra 算法伪代码第10行if语句恒为FALSE）。于是可以一次性取出当前所有距离源节点最近的节点（记载与temp中）计算源节点经过这些点到其邻居节点的距离。于是得到了本小节内容的实现代码。

本小节代码调试结果

输出解释：首先输出了结论；第一张图表表示跳出循环时遍历的结点及其与源节点的距离，其中每一条从1-17从(1,1)到达(9,8)的路径均为最短路径；第二部分按照实验手册要求输出了一条最短路径；第三部分使用数字8以方阵形式输出迷宫及其通路

八、附录

（附源代码，略）

第四部分  致谢

感谢各位读者的阅读。诚然由于个人能管理有限，本实验报告与实现代码还是十分不完善的，敬请谅解，欢迎批评指正。

在写本实验及实验报告时，耳机里适时传来了一首很应景的音乐，于是摘录两句歌词于此，权当纪念

アイムアルーザー なんもないならどうなったっていいだろう

うだうだしてフラフラしていちゃ今に 灰 左様なら

或许从成绩、从CSDN上文章的数据，从很多很多方面，我应该都可以很坦然说アイムアルーザー，但是也会祈愿终有一天能如愿以偿叭。

去思考，去尝试，去突破，去成长

衷心感谢您的阅读，我们下次再见！

标签：Node,temp,迷宫,next,实验,应用,Now,Stack
From： https://blog.csdn.net/2301_80336585/article/details/143010112