需求分析

问题描述

要求使用链栈非递归的形式求解迷宫问题，并用递归的方式求解全部可能的路径。

1. 首先需要写好链栈的相关操作，如初始化，判空，入栈，出栈等等。并且熟练使用栈的相关操作。
2. 其次对于迷宫问题，需要使用非递归的方式，就需要将朴素的递归搜索方式，借助链栈转换成非递归的方式。
3. 对于求出全部可能路径，可以使用类似图的深度优先搜索的方式，依次求解出路径

基本要求

1. 输入的形式和输入值的范围；

   第一行， 两个整数m,n，m代表行数，n代表列数；
   接下来的m行，代表迷宫。
   样例输入：
   4 4
   1 1 1 1
   1 0 0 1
   1 0 0 1
   1 1 1 1

2. 输出的形式；

   m行，输入的迷宫，第m+1行，是否有通路，若有则输出，若无则输出无通路。（若有通路的话） 输出所有走出迷宫可能的路径。

3. 程序所能达到的功能；

   ① 判断迷宫是否有可行的通路，
   ② 输出所有可行的路径。

概要设计

数据结构

1. 三元组point
   三元组(x,y,dir)，其中xy表示坐标，dir表示下一步的方向。
   x∈[1，m],y∈[1，n],dir∈[1,4]。
   其中dir：1 表示向右；2 表示向下；3 表示向左；4 表示向上。
2. 链栈
   
   1. 链栈的节点
      每个节点有两个域，第一个域为point类型的变量，用来保存路径信息，第二个域为指针域，指向下一个栈元素。
   2. 链栈整体
      链栈由栈顶指针和栈底指针组成，附设两个指针方便遍历操作和入栈出栈操作。
   3. 操作集：
      Init(&S) 操作结果：构造一个空栈S。
      IsEmpty(S) 操作结果：若栈为空，返回TRUE，否则返回FALSE。
      GetLength(S) 操作结果：返回S的元素个数。
      GetTop(S，&e) 操作结果：用e返回栈顶元素。
      Push(&S,e) 操作结果： 插入元素e为新的栈顶元素。
      Pop(&S,&e) 操作结果：删除S的栈顶元素，并用e返回其值。
3. 其他
   
   1. 用一个int类型二维数组mp[][]来保存迷宫的01信息。
   2. 用一个int类型二维数组visit[][]来表示是否访问过，0表示未访问，1表示访问过。
   3. 用一个point类型一维数组solution[]来保存任务2的遍历序列。

程序模块

1. Input()与OutPut_Puzzle() 读入迷宫与输出迷宫
2. Solve_1() 检测迷宫是否存在通路，若存在，则将求得的通路以三元组（i，j，d）的形式输出，否则输出“当前迷宫无通路”。
3. OutPut_Path_1() 将Solve_1()中求得的通路输出。若没有，则不执行。
4. Solve_2() 若迷宫中存在通路，则将其存在的所有通路全部输出，每个通路输出一个方阵。若不存在，则不执行。
5. OutPut_Path_2() 将Solve_2()中的每种情况依次输出。

各模块之间的调用关系及算法设计

各模块之间的调用关系

算法设计

1. Input函数
   用双重循环读入迷宫的01序列，保存在一个int型的二维数组当中。
2. OutPut_Puzzle 函数
   同样采用双重循环，将迷宫原样输出。
3. Solve_1函数
   根据第一个任务要求，按照所要求的三元组格式(x,y,dir)输出一条可行路径，否则输出没有可行路径。
   使用链栈非递归的写法。首先将起点入栈，然后利用方向数组(dx[],dy[])与for循环实现上下左右四个方向的探测，若在4次探测中发现一个方向可以继续，则将此步的dir写入栈顶元素，然后将下一步的坐标入栈，退出for循环。 接着判断栈是否为空，若不空继续取栈顶元素，根据栈顶元素再次进行四个方向的探测，如发现有一个方向可以探测成功，则按照上述规则继续处理，若发现四个方向均探测失败，则将栈顶元素出栈，继续取栈顶元素。直到：
   在某一次探测中，发现坐标恰为出口坐标，则说明找到一条通路，返回true。
   尝试了所有探测，均不能到达出口坐标，说明迷宫无解，返回false。
   探测成功的条件（见代码中check函数）包括，坐标不越界，该点未访问（即为0），该点不为障碍物（即不为1）。
4. OutPut_Path_1函数
   若走到出口，则在链栈中保存好了每一步的三元组信息，包括每一步的坐标xy和下一步的方向dir，那么输出路径所要做的只是遍历链栈即可。
   但是由于栈的特性，其顺序是由终点指向起点的，那么则需要借助另一个栈来辅助逆置（代码中的Stemp）,经过逆置后，再遍历栈Stemp即可得到由起点指向终点的三元组序列。
5. Solve_2函数
   若迷宫存在路径(根据Solve_1函数的返回值)，继续调用Solve_2函数，找到所有可行的路径。
   Solve_2首先将visit数组置零，然后调用dfs函数，递归求解。
6. dfs函数
   dfs函数的参数有id,x,y。其中x,y表示当前所访问到的坐标，id表示当前是从起点出发的第几步(从0开始计数)，并且将当前第id步的信息（由x,y,dir构成的三元组），保存到solution[id]中，记录其结果，方便后续输出。
   dfs中同时也是用的是方向数组的四向探测(dx[]与dy[])，若在某一方向探测成功，首先将步骤信息写入solution[id]，然后置visit[x][y]为访问过，接着递归调用dfs(id+1,x,y），直到某一步后走到出后，调用OutPut_Path_2函数。调用完毕后，return回溯到上一层，继续探测其他可能情况。
   在回溯过程中，注意需要将visit[x][y]置为未访问。
7. OutPut_Path_2函数
   由于题目要求第二个任务要输出方阵，那么就要将保存结果的数组solution转换成二维数组。首先将原本的迷宫二维数组mp复制一份给二维数组mpcopy，接着由于solution中保存着三元组(x,y,dir)，则可以直接根据其坐标信息，将mpcopy[x][y]置为dir。
   最后遍历mpcopy，若其元素值为0或1则直接输出，否则的话，根据dir的值，输出上下左右四个方向的箭头即可。

源代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
/*----------------------------------*/
/*对于操作返回值以及链栈进行宏定义*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXSIZE 100
/*----------------------------------*/


/*----------------------------------*/
/*数据类型的定义*/
typedef int Status;
typedef int Boolean;
typedef struct{
    int x,y,dir;
}point; // 点坐标的xy，以及下一步方向dir定义
/*
    对于dir的说明：
    1 表示向右
    2 表示向下
    3 表示向左
    4 表示向上
*/
typedef struct node{
    point point;
    struct node* next;
}Node; // 对于链栈中节点的定义
typedef Node ElemType;
typedef struct{
    Node * top;
    Node * bottom;
}Linkstack,*pLinkstack; // 对于链栈整体的定义

int NoSoutionReason = 0; //1 代表起点为障碍，2代表重点为障碍
int mp[MAXSIZE][MAXSIZE],n,m; // m,n表示迷宫规模，mp用来保存迷宫
int mpcopy[MAXSIZE][MAXSIZE]; // mpcopy用来保存和输出任务2所要求的路径
int visit[MAXSIZE][MAXSIZE];  // visit数组用来保存地图中某点是否访问过
point solution[MAXSIZE];  // solution用来保存任务2的遍历序列
int dx[] = {0,1,0,-1}; // dx为x方向坐标移动数组
int dy[] = {1,0,-1,0}; // dy为y方向坐标移动数组
int StartX = 0,StartY = 0;
int EndX = 0, EndY = 0;

/*----------------------------------*/

/*----------------------------------*/
/*
    链栈的操作
    包括：  初始化，判空，进栈，出栈，取栈顶，求栈长操作。
*/
Status Init(Linkstack &S)
{
    Node * p = (Node *)malloc(sizeof(Node));
    if(!p) return ERROR;
    S.bottom = S.top = p;
    p->next = NULL;
    return OK;
}
Status IsEmpty(Linkstack S)
{
    if(S.bottom == S.top) return TRUE;
    else return FALSE;
}
Status Push(Linkstack & S, ElemType e)
{
    Node * p = (Node *)malloc(sizeof(Node));
    if(!p) return ERROR;
    p->point.x = e.point.x;
    p->point.y = e.point.y;
    p->point.dir = e.point.dir;
    p->next = S.top;
    S.top =  p;
    return OK;
}
Status Pop( Linkstack & S,ElemType & e)
{
    if(S.bottom == S.top) return ERROR;
    Node * p = S.top;
    e.point.x  = p->point.x;
    e.point.y  = p->point.y;
    e.point.dir = p->point.dir;
    S.top = p->next;
    free(p);
    return OK;
}
Status GetTop(Linkstack S, ElemType &e)
{
    if(S.bottom == S.top) return ERROR;
    else {
        e.point.x = S.top->point.x;
        e.point.y = S.top->point.y;
        e.point.dir = S.top->point.dir;
    }
    return OK;
}
Status GetLength(Linkstack S)
{
    Node * p = S.top;
    int cnt = 0;
    while(p != S.bottom){
        cnt++;
        p = p->next;
    }
    return cnt;
}
/*----------------------------------*/

/*----------------------------------*/
/*迷宫求解部分*/
Status OutPut_Path_1(Linkstack S)
{
    /*按照任务1的要求输出(x,y,dir)三元组来表示路径*/
    if(S.top == S.bottom) return ERROR;
    printf("任务1的一条可行路径：");
    Node * p = S.top;
    Linkstack Stemp; //临时栈
    Init(Stemp);
    Node nodetemp;
    /*将栈S中的序列逆置到Stemp中*/
    while(p != S.bottom){
        nodetemp.point.x = p->point.x;
        nodetemp.point.y = p->point.y;
        nodetemp.point.dir = p->point.dir;
        Push(Stemp,nodetemp);
        p=p->next;
    }
    p = Stemp.top;
    /*输出栈Stemp*/
    while(p!= Stemp.bottom){
        printf("(%d,%d,%d) ",p->point.x,p->point.y,p->point.dir);
        p = p->next;
    }
    printf("\n\n");
    return OK;
}
void OutPut_Puzzle()
{
    /*输出迷宫*/
    for(int i = 0; i<m; ++i){
        for(int j = 0; j<n; ++j){
            //printf("%d %d\n",i,j);
            if(i == StartX && j == StartY && mp[i][j] != 1){
                printf("S ");
                continue;
            }
            if(i == EndX && j == EndY && mp[i][j] != 1 ){
                printf("E ");
                continue;
            }
            if(mp[i][j] == 1) printf("■");
            else printf("  ");
        }
        printf("\n");
    }
}
bool check(int x ,int y)
{
    /*检查xy坐标是否越界，以及mp[x][y]是否符合访问规则*/
    if(x<=0||x>m||y<=0||y>n||visit[x][y] == 1||mp[x][y] == 1)
        return false;
    return true;
}
bool Solve_1(Linkstack &S)
{
    /*
        按照任务1的用非递归输出1条路径
        1.首先将起点入栈
        2.然后依次找到下一个访问节点，依次入栈
        3.若当前节点无法拓展，则出栈
        4.直到走到出口，返回true，或者无通路，返回false
    */
    if(mp[StartX][StartY] == 1){
        printf("当前迷宫无通路\n");
        printf("因为入口%d %d为障碍\n",StartX,StartY);
        return false;
    }  //若起点为1， 特判
    if(mp[EndX][EndY] == 1) {
        printf("当前迷宫无通路\n");
        printf("因为出口%d %d为障碍\n",EndX,EndY);
        return false;
    }    //若终点为1， 特判
    point temp = {StartX,StartY,0};
    Node nodetemp = {temp,NULL},nodemem;
    Init(S);
    Push(S,nodetemp);
    visit[StartX][StartY] = 1;
    while(!IsEmpty(S)){
        GetTop(S,nodetemp);
        bool isfind = false;
        if(nodetemp.point.x == EndX && nodetemp.point.y == EndY)
            return true;
        for(int i = 0; i<4;++i){
            int nextx = nodetemp.point.x+dx[i];
            int nexty = nodetemp.point.y+dy[i];
            if(check(nextx,nexty)){
                int dir = i+1;
                Pop(S,nodemem);
                nodemem.point.dir = dir;
                Push(S,nodemem);
                nodetemp.point.x = nextx;
                nodetemp.point.y = nexty;
                nodetemp.point.dir = 0;
                visit[nextx][nexty] = 1;
                Push(S,nodetemp);
                isfind = true;
                break;
            }
        }
        if(!isfind) Pop(S,nodetemp);
    }
    printf("当前迷宫无通路\n");
    return false;
}
void OutPut_Path_2(int id)
{
    /*
        按照任务2的要求，输出所有可能的路径
        1.首先将原mp拷贝给mpcopy
        2.按照solution数组给mpcopy做好标记
        3.输出mpcopy数组
    */
    for(int i = 0 ; i<m;++i)
        for(int j = 0 ; j<n;++j)
            mpcopy[i][j] = mp[i][j];
    for(int i = 0; i<=id;++i){
        point p = solution[i];
        mpcopy[p.x][p.y] = p.dir;
    }
    for(int i = 0 ; i<m;++i){
        for(int j = 0 ; j<n;++j){
            if(i == StartX && j == StartY){
                 printf(" S");
                 continue;
            }
            if(i == EndX && j == EndY){
                printf(" E");
                continue;
            }
            if(mpcopy[i][j] == 2) printf("→");
            else if(mpcopy[i][j] == 3) printf("↓");
            else if(mpcopy[i][j] == 4) printf("←");
            else if(mpcopy[i][j] == 5) printf("↑");
            else if(mpcopy[i][j] == 1) printf("■");
            else printf("  ");
        }
        printf("\n");
    }
    printf("\n");
}
void dfs(int id , int x, int y)
{
    /*
        按照任务2的要求，输出所有可能的路径
        此处dfs搜索的过程
    */
    visit[x][y] = 1;
    for(int i = 0;i<4;++i){
        int nextx = x+dx[i];
        int nexty = y+dy[i];
        if(check(nextx,nexty)){
            visit[nextx][nexty] = 1;//置为访问
            solution[id] = {x,y,i+2};
            if(nextx == EndX && nexty == EndY){
                OutPut_Path_2(id);
                visit[EndX][EndY] = 0;
                return;
            }
            dfs(id+1,nextx,nexty);
            visit[nextx][nexty] = 0;//回溯时置为未访问
        }
    }
}
void Solve_2()
{
    /*
        按照任务2的要求，输出所有可能的路径
        此处为调用dfs函数的过程
    */
    memset(visit,0,sizeof(visit));
    printf("任务2的所有可行解：\n");
    dfs(0,StartX,StartY);

}
void input()
{
    /*输入要处理的地图*/
    memset(mp,0,sizeof(mp));
    memset(visit,0,sizeof(visit));
    printf("所输入的迷宫为\n");
    for(int i = 0; i<m;++i){
        for(int j = 0; j<n;++j){
            scanf("%d",&mp[i][j]);
        }
    }
}
/*----------------------------------*/

int main()
{
    freopen("in.txt.","r",stdin);
    //freopen("out.txt","w",stdout);
    Linkstack S;
    int kase = 1;
    while(scanf("%d %d",&m,&n) != EOF){
        int NoSoutionReason = 0;
        printf("/*----------------------------------*/\n");
        printf("Case %d \n",kase++);
        scanf("%d %d",&StartX,&StartY);
        scanf("%d %d",&EndX,&EndY);
        printf("%d %d %d %d\n",StartX,StartY,EndX,EndY);
        input();
        OutPut_Puzzle();
        if(Solve_1(S)){
            OutPut_Path_1(S);
            Solve_2();
        }
        printf("\n");
    }
    return 0;
}

数据测试与分析

注：其中→代表向右走，←代表向左走，↑代表向上走，↓代表向下走。

Case 1
4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Case 2
4 4
1 1 1 1
1 1 0 1
1 0 0 1
1 1 1 1

Case 5
7 7
1 1 1 1 1 1 1 
1 0 0 1 0 0 1
1 0 1 0 0 0 1
1 0 0 1 0 0 1
1 0 1 1 0 1 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

Case 6 （课本P50 图3.4所示迷宫）
10 10
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 1 1 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1