迷宫问题 192132-01

迷宫问题
以一个 m*n 的长方阵表示迷宫， 0 和 1
分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
要求：
（ 1 ）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组 (i,j,d) 的形式输出，其中 (i,j)
指示迷宫中的一个坐标， d 表示走到下一坐标的方向。
（ 2 ）测试几组数据，数据的规模由小变大，即网格越来越小，障碍越来越复杂。
（ 3 ）实现该问题的可视化界面。
#include<stdio.h>     
#include<iostream>     
#include<math.h>     
#include<stdlib.h>     
#include<ctype.h>     
#include<algorithm>     
#include<vector>     
#include<string.h>     
#include<stack>     
#include<set>     
#include<map>     
#include<sstream>     
#include<time.h>     
#include<utility>     
#include<malloc.h>     
#include<stdexcept>     
#include<iomanip>     
#include<iterator>     

using namespace std;  

int n, m, sx, sy, ex, ey, t;  
int p[110][110];  
char MAP[110][110];
int vis[110][110];  
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };  

struct node  
{  
    int x;  
    int y;  
};  

struct node pre[30][30];//存储节点前一个位置   


//////////////////////////  栈   
#define DataType node                  

struct Node;                         
typedef struct Node *PNode;           

typedef struct Node                   
{  
    DataType info;                  
    PNode link;                     
}Node;  

typedef struct LinkStack             
{  
    PNode top;          
}LinkStack;  

typedef struct LinkStack * PLinkStack;     
PLinkStack createEmptyStack(void);  
int isEmptyStack(PLinkStack stack);  
int push(PLinkStack stack, DataType x);  
int pop(PLinkStack stack);  
DataType getTop(PLinkStack stack);  
void showStack(PLinkStack stack);  
void setEmpty(PLinkStack stack);  
void destroyStack(PLinkStack stack);  

PLinkStack createEmptyStack(void)  
{  
    PLinkStack stack = (PLinkStack)malloc(sizeof(struct LinkStack));  
    if (stack == NULL)  
        printf("存储分配失败，请重建栈！\n");  
    else  
        stack->top = NULL;  
    return stack;  
}  

int isEmptyStack(PLinkStack stack)  
{  
    return (stack->top == NULL);  
}  

int push(PLinkStack stack, DataType x)  
{  
    PNode p = (PNode)malloc(sizeof(struct Node));  
    if (p == NULL)  
    {  
        printf("新结点分配内存失败，进栈失败，请重试！\n");  
        return 0;  
    }  
    else  
    {  
        p->info = x;  
        p->link = stack->top;       
        stack->top = p;  
        return 1;  
    }  
}  

int pop(PLinkStack stack)  
{  
    if (isEmptyStack(stack))  
    {  
        printf("栈为空！\n");  
        return 0;  
    }  
    else  
    {  
        PNode p;  
        p = stack->top;   //删除最后一个结点     
        stack->top = stack->top->link;  
        free(p);  
        return 1;  
    }  
}  

DataType getTop(PLinkStack stack)  
{  
    if (isEmptyStack(stack))  
    {  
        printf("栈为空！取栈顶元素失败！\n");  
    }  
    return (stack->top->info);  
}  

void showStack(PLinkStack stack)  
{  
    if (isEmptyStack(stack))  
        printf("当前栈为空！无内容可显示。\n");  
    else  
    {  
        PNode p;  
        p = stack->top;  
        printf("顶--> ");  
        while (p->link != NULL)  
        {  
            printf("%d ", p->info);  
            p = p->link;  
        }  
        printf("%d ", p->info);     
        printf("-->底\n");  
    }  
}  

void setEmpty(PLinkStack stack)  
{  
    stack->top = NULL;  
}  

void destroyStack(PLinkStack stack)  
{  
    if (stack)  
    {  
        stack->top = NULL;  
        free(stack);  
    }  
}  
///////////////////////////   

int check(int x, int y)  
{  
    if (x >= 0 && x < m && y >= 0 && y < n)  
        return 1;  
    return 0;  
}  

void printf_path()  
{  
    node ss,sss;  

    DataType data;  
    PLinkStack stack;  

    stack = createEmptyStack();  

    ss.x = ex;  
    ss.y = ey;  

    while (1)  
    {  
        push(stack, ss);  
        if (ss.x == sx && ss.y == sy)  
            break;  
        ss = pre[ss.x][ss.y];  
    }  

    int pres, presy;  
    printf ("           行走路径 文字描述如下：\n\n\n");
    while (!(isEmptyStack(stack)))  
    {  
        ss = getTop(stack);  
        pop(stack);  
        MAP[ss.x+1][ss.y+1] = '*';
        if (!(isEmptyStack(stack)))  
            sss = getTop(stack);  
        printf("           ");printf("此刻坐标(%d, %d)  ", ss.x, ss.y);  

        if (!(isEmptyStack(stack)))  
        {  
            if (sss.x == ss.x && sss.y == ss.y + 1)  
                    printf("向右走\n"); 
            if (sss.x == ss.x && sss.y == sss.y - 1)  
                    printf("向左走\n");  

            if (sss.x == ss.x + 1 && sss.y == sss.y)  
                    printf("向下走\n");
            if (sss.x == ss.x - 1 && sss.y == sss.y)  
                    printf("向上走\n"); 
        }  
    }printf("到达终点!\n\n\n\n");  
    printf ("           行走路径图如下：\n");

    for(int i=0;i<=m+1;i++)
    {
        printf("           ");
        for(int j=0;j<=n+1;j++)
        {
            if (j==0 || j== n+1)
                printf("| ");
            else if (i == 0 || i == m+1)
                printf("—");
            else 
                printf("%c ",MAP[i][j]);
        }
        printf("\n");
    }
}  

////////////////////////队列   

#define Error( str )        FatalError( str )   
#define FatalError( str )   fprintf( stderr, "%s\n", str ), exit( 1 )   
#define  ElementType node   

#define MAXQUEUE 100   

typedef struct NODE  
{  
    ElementType data;  
    struct NODE* nextNode;  
} NODE;  
typedef struct queue  
{  
    NODE* front;    // 对首指针   
    NODE* rear;     // 队尾指针   
    int items;      // 队列中项目个数   

} *ptrQueue;  
typedef ptrQueue Queue;  
int IsEmpty(Queue q);  
int IsFull(Queue q);  
Queue CreateQueue(void);  
void DisposeQueue(Queue q);  
void MakeEmpty(Queue q);  
void Enqueue(ElementType x, Queue q);  
ElementType Front(Queue q);  
void Dequeue(Queue q);  

int IsFull(Queue q)  
{  
    return q->items == MAXQUEUE;  
}  

int IsEmpty(Queue q)  
{  
    return q->items == 0;  
}  
Queue CreateQueue(void)  
{  
    Queue q;  

    q = (Queue)malloc(sizeof(struct NODE));  
    if (NULL == q)  
        Error("空间不足，队列内存分配失败！");  

    q->front = (NODE*)malloc(sizeof(NODE));  
    if (NULL == q->front)  
        Error("空间不足，队列首节点内存分配失败！");  

    q->rear = (NODE*)malloc(sizeof(NODE));  
    if (NULL == q->rear)  
        Error("空间不足，队列尾节点内存分配失败！");  

    q->items = 0;  

    return q;  
}  

void DisposeQueue(Queue q)  
{  
    MakeEmpty(q);  
    free(q);  
}  

void MakeEmpty(Queue q)  
{  
    if (q == NULL)  
        Error("必须先使用CreateQueue创建队列！");  

    while (IsEmpty(q))  
        Dequeue(q);  
}  

void Enqueue(ElementType x, Queue q)  
{  
    if (IsFull(q))  
        Error("队列已满！");  

    NODE* pnode;  
    pnode = (NODE*)malloc(sizeof(NODE));  
    if (NULL == pnode)  
        Error("新节点分配内存失败！");  

    pnode->data = x;  
    pnode->nextNode = NULL;  
    if (IsEmpty(q))  
        q->front = pnode;           // 项目位于首端   
    else  
        q->rear->nextNode = pnode;  // 链接到队列尾端   
    q->rear = pnode;                    // 记录队列尾端的位置   
    q->items++;                     // 项目数加1   

    return;  
}  

void Dequeue(Queue q)  
{  
    if (IsEmpty(q))  
        Error("队列本身为空！");  

    NODE* pnode;  
    pnode = q->front;  
    q->front = q->front->nextNode;  
    free(pnode);  

    q->items--;  
    if (q->items == 0)  
        q->rear = NULL;  

    return;  
}  

ElementType Front(Queue q)  
{  
    if (!IsEmpty(q))  
        return q->front->data;  
    Error("队列为空\n");  
}  

ElementType FrontAndDequeue(Queue q)  
{  
    ElementType x;  

    if (IsEmpty(q))  
        Error("队列为空！");  
    else  
    {  
        q->items--;  
        x = q->front->data;  
        q->front = q->front->nextNode;  
    }  

    return x;  
}  

///////////////////////   

int bfs()  
{  
    memset(vis, 0, sizeof(vis));  

    Queue sqQueue;  
    sqQueue = CreateQueue();  

    node qq, qqq;  

    qq.x = sx;  
    qq.y = sy;  
    vis[sx][sy] = 1;  

    Enqueue(qq, sqQueue);  

    while (!IsEmpty(sqQueue))  
    {  
        qq = Front(sqQueue);  
        Dequeue(sqQueue);  

        if (qq.x == ex && qq.y == ey)  
        {  
            printf_path();  
            return 1;  
        }  

        for (int i = 0; i < 4; i++)  
        {  
            int x = qq.x + dir[i][0];  
            int y = qq.y + dir[i][1];  

            if (!check(x, y) || vis[x][y] || p[x][y] == 1)  
                continue;  

            qqq = qq;  
            qqq.x = x;  
            qqq.y = y;  

            pre[qqq.x][qqq.y] = qq;  

            vis[x][y] = 1;  
            Enqueue(qqq, sqQueue);  
        }  
    }  
    return 0;  
}  


int main()  
{  
    printf("请输入迷宫长和宽\n");  
    while (cin >> m >> n)  
    {  
        printf("输入起点坐标和终点坐标\n");  
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);  
        printf("请输入迷宫\n");  
        for (int i = 0; i < m; i++)  
        {  
            for (int j = 0; j < n; j++)  
            {  
                cin >> p[i][j];  
                MAP[i+1][j+1] = p[i][j] + '0';
            }  
        }  
        int ans = bfs();  
        if (ans == 0)  
            printf("不存在起点到终点的通路\n\n\n\n");  
        printf("\n\n\n\n");  
        printf("是否继续 1.yes 2.no\n ");  
        scanf("%d",&t);  
        if (t == 2) { printf("          再见   ,谢谢使用本系统！\n\n\n"); return 0; }  
        printf("\n\n\n\n");  
        printf("请输入迷宫长和宽\n");  
    }  
    return 0;  
}
测试数据：
5 5
0 0 4 4
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 1 0
1
5 5
0 0 4 4
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0