vlambda博客
学习文章列表

#include <stdio.h>
#define SIZE 1024
struct Box { int x; //点的横坐标 int y; //点的纵坐标 int dir; //下一个点的方向};typedef struct Box Box;
typedef struct{ Box data[SIZE]; int top;}Stack;
//用二位数组表示迷宫，0表示可以走，1表示不可以走int map[6][6] = {  {0, 0, 0, 1, 0, 1},  {0, 1, 0, 0, 1, 0},  {0, 0, 1, 0, 0, 0},  {0, 1, 0, 1, 1, 0},  {0, 1, 0, 1, 0, 0},  {0, 0, 0, 0, 0, 0}};
//初始化顺序栈int InitStack(Stack *s) { if (!s) return -1;  s->top = -1; return 0;}
//检查该点是否可以走，1表示不能走，超出地图也不能走int check(Box b){ if (b.x < 0 || b.x > 5 || b.y < 0 || b.y > 5) //点不在迷宫内 return -1; if (map[b.x][b.y] != 0) //点不能走 return -1; return 1;}
//进栈操作int push(Stack *s, Box b){ if (s->top == SIZE - 1 || !s) return -1; s->top++; s->data[s->top] = b; return 0;}
//判断栈是否为空int EmptyStack(Stack *s){ if (!s) return -1; return (s->top == -1) ? 1 : 0;}
//获取栈顶元素int GetTop(Stack *s, Box *b){ if (!s || s->top == -1) return -1; *b = s->data[s->top]; return 0;}
//显示一条可以走得通的路径（路径保存在栈中，遍历栈可以得到路径）void ShowPath(Stack *s){ int i; for (i = 0; i <= s->top; i++) { printf("(%d %d)", s->data[i].x, s->data[i].y); if (i != s->top) { printf("->"); } } printf("\n");}
//出栈操作int pop(Stack *s, Box *b){ if (!s || s->top == -1) return -1; *b = s->data[s->top]; s->top--; return 0;}
//修改栈顶元素，下一个点的位置int ChangeDir(Stack *s, int dir){ if (!s || s->top == -1) return -1; s->data[s->top].dir = dir; return 0;}
//x1 y1表示起点 x2，y2表示终点int Walk(Stack *s, int x1, int y1, int x2, int y2){ Box now, t; int i, j;
 now.x = x1; now.y = y1; now.dir = -1;
 if (check(now) == 1) {        push(s, now);                  //如果该点可以走，则进栈 map[now.x][now.y] = -1; //表示点走过 }
 while (EmptyStack(s) != 1) { GetTop(s, &now); //获取栈顶的点 if (now.x == x2 && now.y == y2) //栈顶元素就是终点 { ShowPath(s); map[now.x][now.y] = 0; //表示点没走过 pop(s, &now);            GetTop(s, &now)； } else { int k; for (k = now.dir + 1; k < 4; k++) //判断每个方向是否可走 { switch(k) { case 0: //向上走 i = now.x - 1; j = now.y; break; case 1: i = now.x; j = now.y + 1; break; case 2: //向下 i = now.x + 1; j = now.y; break; case 3: //向左 i = now.x; j = now.y - 1; break; } t.x = i; t.y = j; t.dir = -1; if (check(t) == 1) { ChangeDir(s, k); push(s, t); map[i][j] = -1; break; } } if (k == 4) //没有方向可以走 { pop(s, &now); //无路可走，出栈 map[now.x][now.y] = 0; } } }}
int main(){ Stack stack;
 InitStack(&stack);
 Walk(&stack, 0, 0, 5, 5);
 return 0;}