1 #include2 #include 3 typedef enum { ERROR, OK } Status; 4 typedef struct 5 { 6 int row, line; 7 }PosType; 8 9 typedef struct 10 { 11 int di, ord; 12 PosType seat; 13 }SElemType; 14 15 typedef struct 16 { 17 SElemType * base; 18 SElemType * top; 19 int stacksize; 20 }SqStack; 21 22 Status InitStack(SqStack &S); 23 Status Push(SqStack &S, SElemType &a); 24 Status Pop(SqStack &S, SElemType &a); 25 Status StackEmpty(SqStack S); 26 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end); 27 void Initmaze(int maze[12][12], int size); 28 void printmaze(int maze[12][12], int size); 29 Status Pass(int maze[12][12], PosType CurPos); 30 void Markfoot(int maze[12][12], PosType CurPos); 31 PosType NextPos(PosType CurPos, int Dir); 32 void printpath(int maze[12][12], SqStack S, int size); 33 void main(void) 34 { 35 SqStack S; 36 int size, maze[12][12]; 37 for (int n = 0; n < 10; n++) 38 { 39 printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):\n"); 40 scanf_s("%d", &size); 41 if (size < 1 || size>10) 42 { 43 printf("输入错误!"); 44 return; 45 } 46 Initmaze(maze, size); 47 printmaze(maze, size); 48 PosType start, end; 49 printf("输入入口行坐标和列坐标:"); 50 scanf_s("%d", &start.row); 51 scanf_s("%d", &start.line); 52 printf("输入出口行坐标和列坐标:"); 53 scanf_s("%d", &end.row); 54 scanf_s("%d", &end.line); 55 if (MazePath(maze, S, start, end)) 56 printpath(maze, S, size); 57 else 58 printf("找不到通路!\n\n"); 59 } 60 } 61 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end) 62 { 63 PosType curpos; 64 int curstep; 65 SElemType e; 66 InitStack(S); 67 curpos = start; 68 curstep = 1; 69 do { 70 if (Pass(maze, curpos)) 71 { 72 Markfoot(maze, curpos);//如果0可以通过，则标记为1 73 e.di = 1;//从第一个方向开始 74 e.ord = curstep; 75 e.seat = curpos; 76 Push(S, e);//放入栈S 77 if (curpos.row == end.row && curpos.line == end.line)//到达目的地，成功 78 return OK; 79 curpos = NextPos(curpos, 1);//继续向下一个探索 80 curstep++; 81 } 82 else//不能通过的情况 83 { 84 if (!StackEmpty(S))//栈不为空 85 { 86 Pop(S, e);//弹出栈元素，改变方向 87 while (e.di == 4 && !StackEmpty(S)) 88 { 89 Markfoot(maze, e.seat);//标记为1 90 Pop(S, e);//弹出e 91 } 92 if (e.di < 4) 93 { 94 e.di++; 95 Push(S, e); 96 curpos = NextPos(e.seat, e.di); 97 } 98 } 99 }100 } while (!StackEmpty(S));101 return ERROR;102 }103 void Initmaze(int maze[12][12], int size)104 {105 char select;106 printf("选择创建方式 A:自动生成 B:手动创建\n");107 label:scanf_s("%c", &select);108 if (select == 'a' || select == 'A')109 {110 for (int i = 0; i < size + 2; i++)111 maze[0][i] = 1;112 for (int i = 1; i < size + 1; i++)113 {114 maze[i][0] = 1;115 for (int j = 1; j < size + 1; j++)116 maze[i][j] = rand() % 2;117 maze[i][size + 1] = 1;118 }119 for (int i = 0; i < size + 2; i++)120 maze[size + 1][i] = 1;121 }122 else if (select == 'b' || select == 'B')123 {124 printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n", size, size);125 for (int i = 0; i < size + 2; i++)maze[0][i] = 1;126 for (int i = 1; i < size + 1; i++)127 {128 maze[i][0] = 1;129 for (int j = 1; j < size + 1; j++)130 scanf_s("%d", &maze[i][j]);131 maze[i][size + 1] = 1;132 }133 for (int i = 0; i < size + 2; i++)134 maze[size + 1][i] = 1;135 }136 else if (select == '\n')137 goto label;138 else printf("输入错误!");139 }140 void printmaze(int maze[12][12], int size)//141 {142 printf("\n\n");143 printf("显示所建的迷宫(#表示外面的墙):\n");144 for (int i = 0; i < size + 2; i++)145 printf("%c ", '#');146 printf("\n");147 for (int i = 1; i < size + 1; i++)148 {149 printf("%c ", '#');150 for (int j = 1; j < size + 1; j++)151 {152 printf("%d ", maze[i][j]);153 }154 printf("%c", '#');155 printf("\n");156 }157 for (int i = 0; i < size + 2; i++)158 printf("%c ", '#');159 printf("\n");160 161 }162 163 void printpath(int maze[12][12], SqStack S, int size)164 {165 printf("\n\n通路路径为:\n");166 SElemType * p = S.base;167 while (p != S.top)168 {169 maze[p->seat.row][p->seat.line] = 2;170 p++;171 }172 for (int i = 0; i < size + 2; i++)173 printf("%c ", '#'); printf("\n");174 for (int i = 1; i < size + 1; i++)175 {176 printf("%c ", '#');177 for (int j = 1; j < size + 1; j++)178 {179 if (maze[i][j] == 2) 180 printf("%c ", '0');181 else 182 printf(" ");183 }184 printf("%c", '#');185 printf("\n");186 }187 for (int i = 0; i < size + 2; i++)188 printf("%c ", '#'); 189 printf("\n\n");190 191 }192 193 Status Pass(int maze[12][12], PosType CurPos)194 {195 if (maze[CurPos.row][CurPos.line] == 0)196 return OK;197 else 198 return ERROR;199 }200 void Markfoot(int maze[12][12], PosType CurPos)201 {202 maze[CurPos.row][CurPos.line] = 1;203 }204 PosType NextPos(PosType CurPos, int Dir)205 {206 PosType ReturnPos;207 switch (Dir)208 {209 case 1:210 ReturnPos.row = CurPos.row;211 ReturnPos.line = CurPos.line + 1;212 break;213 case 2:214 ReturnPos.row = CurPos.row + 1;215 ReturnPos.line = CurPos.line;216 break;217 case 3:218 ReturnPos.row = CurPos.row;219 ReturnPos.line = CurPos.line - 1;220 break;221 case 4:222 ReturnPos.row = CurPos.row - 1;223 ReturnPos.line = CurPos.line;224 break;225 }226 return ReturnPos;227 }228 Status InitStack(SqStack &S)229 {230 S.base = (SElemType *) malloc(100 * sizeof(SElemType));231 if (!S.base)return ERROR;232 S.top = S.base;233 S.stacksize = 100;234 return OK;235 }236 Status Push(SqStack &S, SElemType &a)237 {238 *S.top++ = a;239 return OK;240 }241 Status Pop(SqStack &S, SElemType &a)242 {243 if (S.top == S.base)244 return ERROR;245 a = *--S.top;246 return OK;247 }248 249 Status StackEmpty(SqStack S)250 {251 if (S.top == S.base)252 return OK;253 return ERROR;254 }