【问题描述】
以一个mXn的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【任务要求】
实现链栈求解迷宫从入口到出口的一条可行通路。
【测试数据】
迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。
代码：
#include <stdio.h> #include <stdlib.h> typedef struct node { int X; int Y; struct node *next; }NODE; typedef struct { struct NODE *top; int cnt; }STACK; STACK *Creatstack()//创建链栈 { STACK *S; S = (STACK *)malloc(sizeof(STACK)); if (S == NULL) { printf("创建失败"); exit(1); } else { S->top = NULL; S->cnt = 0; } return S; } void Iputstack(STACK *S, int x, int y) { NODE *s; s = (NODE *)malloc(sizeof(NODE)); if (s != NULL) { s->X = x; s->Y = y; s->next = S->top;//S->top是和s同样类型的结点,将新结点的后继指向一个地址（这个地址其实可以看成是单链表的头结点看待） S->top = s;//给指向的地址复制，其实可以看成是把栈顶指针指向新结点 S->cnt++; } } void Outstack(STACK *S) { if (S->top != NULL) { NODE *s,*p; s = S->top; p=s->next; free(s); S->top = p; S->cnt--; } } int main() { int i; STACK *S; NODE *p; int Hx, Hy, Ex, Ey,Px,Py; S = Creatstack(); int M[10][10] = { { 1,0,1,1,1,1,1,1,1,1 }, { 1,0,0,1,0,0,0,1,0,1 }, { 1,0,0,1,0,0,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,0 }, { 1,1,1,1,1,1,1,1,1,1 } }; Hx= 0; Hy = 1; Ex = 8; Ey = 9; Px = Hx, Py = Hy; Iputstack(S, Hx, Hy); while (S->top != NULL)//栈空表示无路可走 { p = S->top;//每次循环都把栈中的栈顶的地址给p Px = p->X; Py = p->Y;//把栈顶的X,Y值取出来作为本次循环的起始坐标点 if (Px == Ex&&Py == Ey)//找到出口，跳出循环 break; if (M[Px-1][Py] == 0)//上方向 { Iputstack(S, Px-1, Py);//满足条件的入栈，下面代码同理 M[Px - 1][Py] = 2;//表示走过 } else if (M[Px + 1][Py] == 0)//下方向 { Iputstack(S, Px+1, Py); M[Px + 1][Py] = 2;//表示走过 } else if (M[Px][Py-1] == 0)//左方向 { Iputstack(S, Px-1, Py); M[Px][Py-1] = 2;//表示走过 } else if (M[Px][Py+1] == 0)//右方向 { Iputstack(S, Px, Py+1); M[Px][Py+1] = 2;//表示走过 } else { Outstack(S); M[Px][Py] = 3; } } p = S->top;//p指向栈顶 for (i = 0; i < S->cnt; i++)//输出栈中值 { printf("（%d，%d）\n", p->X, p->Y); p = p->next;//p每次循环完指向后继结点 } return 0; }
