爱吃西瓜皮

😘Stack.h
#include<stdio.h>
#include<malloc.h>
#include
#define MaxSize 100

typedef struct
{
int i; //当前方块的行号
int j; //当前方块的列号
int di; //di是下一可走相邻方位的方位号
} Box;
typedef Box ElemType;

typedef struct
{
Box data[MaxSize];
int top; //栈顶指针
} StType; //定义栈类型
void InitStack(StType*& s)
{
s = (StType*)malloc(sizeof(StType));
s->top = -1;
}
bool StackEmpty(StType* s)
{
return(s->top == -1);
}
bool Push(StType*& s, ElemType e)
{
if (s->top == MaxSize - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(StType*& s, ElemType& e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
}
bool GetTop(StType* s, ElemType& e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
}
void DestroyStack(StType*& s)
{
free(s);
}

typedef double ElemType1;
typedef struct linknode
{
ElemType1 data; //数据域
struct linknode* next; //指针域
} LinkStNode; //链栈类型
void InitStack1(LinkStNode*& s)
{
s = (LinkStNode*)malloc(sizeof(LinkStNode));
s->next = NULL;
}
void DestroyStack1(LinkStNode*& s)
{
LinkStNode* pre = s,p=s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
bool StackEmpty1(LinkStNode s)
{
return(s->next == NULL);
}
bool Push1(LinkStNode*& s, ElemType1 e)
{
LinkStNode* p;
p = (LinkStNode*)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
return true;
}
bool Pop1(LinkStNode*& s, ElemType1& e)
{
LinkStNode* p;
if (s->next == NULL)
return false;
p = s->next;
e = p->data;
s->next = p->next;
free(p);
return true;
}
bool GetTop1(LinkStNode* s, ElemType1& e)
{
if (s->next == NULL)
return false;
e = s->next->data;
return true;
}
🤡mg1.h
#include "Stack.h"
#define MaxSize 100
#define M 8
#define N 8
int mg[M + 2][N + 2] =
{
{1,1,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,1},{1,1,1,1,1,1,1,1,1,1} };

bool mgpath(int xi, int yi, int xe, int ye)
{
Box path[MaxSize], e;
int i, j, di, i1, j1, k;
bool find;
StType* st;
InitStack(st);
e.i = xi; e.j = yi; e.di = -1;
Push(st, e);
mg[xi][yi] = -1;
while (!StackEmpty(st))
{
GetTop(st, e);
i = e.i; j = e.j; di = e.di;
if (i == xe && j == ye)
{
printf("一条迷宫路径如下:\n");
k = 0;
while (!StackEmpty(st))
{
Pop(st, e);
path[k++] = e;
}
while (k >= 1)
{
k--;
printf("\t(%d,%d)", path[k].i, path[k].j);
if ((k + 2) % 5 == 0)
printf("\n");
}
printf("\n");
DestroyStack(st);
return true;
}
find = false;
while (di < 4 && !find)
{
di++;
switch (di)
{
case 0:i1 = i - 1; j1 = j; break;
case 1:i1 = i; j1 = j + 1; break;
case 2:i1 = i + 1; j1 = j; break;
case 3:i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0)find = true;
}
if (find)
{
st->data[st->top].di = di;
e.i = i1; e.j = j1; e.di = -1;
Push(st, e);
mg[i1][j1] = -1;
}
else
{
Pop(st, e);
mg[e.i][e.j] = 0;
}
}
DestroyStack(st);
return false;
}
😰主函数mg1.cpp
#include "mg1.h"
int main()
{
if (!mgpath(1, 1, M, N))
printf("该迷宫问题没有解");

}