迷宫问题
以一个
要求：
（
（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];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 nodestruct 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");elsestack->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 = 4;ss.y = 4;while (1){push(stack, ss);if (ss.x == sx && ss.y == sy)break;ss = pre[ss.x][ss.y];}int pres, presy;while (!(isEmptyStack(stack))){ss = getTop(stack);pop(stack);if (!(isEmptyStack(stack)))sss = getTop(stack);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");}////////////////////////队列#define Error( str )FatalError( str )#define FatalError( str ) fprintf( stderr, "%s\n", str ), exit( 1 )#define ElementType node#define MAXQUEUE 100typedef 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;// 项目位于首端elseq->rear->nextNode = pnode; // 链接到队列尾端q->rear = pnode;// 记录队列尾端的位置q->items++;// 项目数加1return;}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];}}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;}
测试数据：
原来和文字沾上边的孩子从来都是不快乐的，
