请教高手C++数据结构回溯算法解，迷宫问题

Question

迷宫有两个门，一个叫做入口，一个叫做出口。把一个老鼠从一个无顶盖的大盒子的入口赶进迷宫。迷宫中设置很多隔壁。对前进的方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。求解迷宫问题，即找从入口到出口的路径。
【提示】对于迷宫问题，可使用栈这种数据结构实现，二维迷宫可通过矩阵表示，从出发点开始，每个点按照四个邻域计算，按照右，上，左，下的顺序搜索下一落脚点，有路则进，无路即退回前点再从下一个方向搜索。

Answer 1

//迷宫用栈做的
#include "stdio.h"
#include "stdlib.h"
#define INITSIZE 100
#define STACKINCRESMENT 10
#define WALL 9999
struct stack
{
int *base;
int *top;
int size;
};

struct mi
{
int val;
bool tag;
int di;
};

void init_stack(stack *);
void push(stack*,int);
int pop(stack*);
int getop(stack*);
int palace(stack*, mi p[10][10]);

int main()
{
int e;
int ch;
struct mi p[10][10];
for(int i=0;i<10;i++)
{
p[0][i].val = 0;
p[i][0].val = 0;
p[9][i].val = 0;
p[i][9].val = 0;
}
for(int j=1;j<9;j++)
{
for(int k=1;k<9;k++)
{
p[j][k].val = 1;
}
}
p[1][3].val = p[1][7].val =0;
p[2][3].val = p[2][7].val =0;
p[3][5].val = p[3][6].val =0;
p[4][2].val = p[4][3].val = p[4][4].val =0;
p[5][4].val = 0;
p[6][2].val = p[6][6].val =0;
p[7][2].val = p[7][3].val = p[7][4].val =0;
p[7][6].val = p[7][7].val =0;
p[8][1].val = 0;

for(int m=0;m<10;m++)
{
for(int n=0;n<10;n++)
{
printf(" %d ",p[m][n]);
p[m][n].tag =0;
p[m][n].di =0;
}
printf("\n");
}

struct stack *s = (stack*)malloc(sizeof(stack));
init_stack(s);
palace(s, p);

printf("\none path is: \n");
for(int a=0;*s->base<89;s->base++)
{
printf("-a");
printf("%d",*s->base);

}

return 0;
}

void init_stack(stack *s)
{
s->base = (int*)malloc(INITSIZE*sizeof(stack));
if(!s->base) printf("malloc error:");
*s->base++ = 0;//栈底为0
s->top = s->base;
s->size = INITSIZE;
}

void push(stack* s, int e)
{
if(s->top - s->base >= INITSIZE)
{
s->base = (int*)realloc(s->base,(s->size+STACKINCRESMENT)*sizeof(stack));
s->top = s->base + s->size;
s->size += STACKINCRESMENT;
}
*s->top++ = e;
}

int pop(stack* s)
{
if(s->top == s->base) printf("error\n");
int e = 0;
e = *--s->top;
*s->top = NULL;
return e;
}

int getop(stack* s)
{
if(s->top == s->base) printf("error\n");
int e = 0;
stack *p = s;
e = *(--p->top);
++p->top;
return e;
}

int palace(stack* s, mi p[10][10])
{
int i=1;
int j=1;
int k;
int r;
push(s,i*10+j);
j++;
do
{
r=getop(s);
if(r==88) return 0;
if(p[i][j].val>0 && p[i][j].di<1)
{
push(s,i*10+j);
p[i][j].tag = 1;
p[i][j].di = 1;
j++;
}
else
{
k = getop(s);
i = k/10;
j = k%10;
if(p[i][j].di==1 && (p[i][j].val>0))
{
p[i][j].di++;
i++;
}
if(p[i][j].di==2 && (p[i][j].val>0))
{
p[i][j].di++;
j--;
if(p[i][j].di>0) { k = pop(s);}
}
}

}while(1);
}

Answer 2

//迷宫用栈做的
#include
"stdio.h"
#include
"stdlib.h"
#define
INITSIZE
100
#define
STACKINCRESMENT
10
#define
WALL
9999
struct
stack
{
int
*base;
int
*top;
int
size;
};
struct
mi
{
int
val;
bool
tag;
int
di;
};
void
init_stack(stack
*);
void
push(stack*,int);
int
pop(stack*);
int
getop(stack*);
int
palace(stack*,
mi
p[10][10]);
int
main()
{
int
e;
int
ch;
struct
mi
p[10][10];
for(int
i=0;i<10;i++)
{
p[0][i].val
=
0;
p[i][0].val
=
0;
p[9][i].val
=
0;
p[i][9].val
=
0;
}
for(int
j=1;j<9;j++)
{
for(int
k=1;k<9;k++)
{
p[j][k].val
=
1;
}
}
p[1][3].val
=
p[1][7].val
=0;
p[2][3].val
=
p[2][7].val
=0;
p[3][5].val
=
p[3][6].val
=0;
p[4][2].val
=
p[4][3].val
=
p[4][4].val
=0;
p[5][4].val
=
0;
p[6][2].val
=
p[6][6].val
=0;
p[7][2].val
=
p[7][3].val
=
p[7][4].val
=0;
p[7][6].val
=
p[7][7].val
=0;
p[8][1].val
=
0;
for(int
m=0;m<10;m++)
{
for(int
n=0;n<10;n++)
{
printf("
%d
",p[m][n]);
p[m][n].tag
=0;
p[m][n].di
=0;
}
printf("\n");
}
struct
stack
*s
=
(stack*)malloc(sizeof(stack));
init_stack(s);
palace(s,
p);
printf("\none
path
is:
\n");
for(int
a=0;*s->base<89;s->base++)
{
printf("-a");
printf("%d",*s->base);
}
return
0;
}
void
init_stack(stack
*s)
{
s->base
=
(int*)malloc(INITSIZE*sizeof(stack));
if(!s->base)
printf("malloc
error:");
*s->base++
=
0;//栈底为0
s->top
=
s->base;
s->size
=
INITSIZE;
}
void
push(stack*
s,
int
e)
{
if(s->top
-
s->base
>=
INITSIZE)
{
s->base
=
(int*)realloc(s->base,(s->size+STACKINCRESMENT)*sizeof(stack));
s->top
=
s->base
+
s->size;
s->size
+=
STACKINCRESMENT;
}
*s->top++
=
e;
}
int
pop(stack*
s)
{
if(s->top
==
s->base)
printf("error\n");
int
e
=
0;
e
=
*--s->top;
*s->top
=
NULL;
return
e;
}
int
getop(stack*
s)
{
if(s->top
==
s->base)
printf("error\n");
int
e
=
0;
stack
*p
=
s;
e
=
*(--p->top);
++p->top;
return
e;
}
int
palace(stack*
s,
mi
p[10][10])
{
int
i=1;
int
j=1;
int
k;
int
r;
push(s,i*10+j);
j++;
do
{
r=getop(s);
if(r==88)
return
0;
if(p[i][j].val>0
&&
p[i][j].di<1)
{
push(s,i*10+j);
p[i][j].tag
=
1;
p[i][j].di
=
1;
j++;
}
else
{
k
=
getop(s);
i
=
k/10;
j
=
k%10;
if(p[i][j].di==1
&&
(p[i][j].val>0))
{
p[i][j].di++;
i++;
}
if(p[i][j].di==2
&&
(p[i][j].val>0))
{
p[i][j].di++;
j--;
if(p[i][j].di>0)
{
k
=
pop(s);}
}
}
}while(1);
}

Answer 3

广搜即可。

Answer 4

用图论中的广度优先搜索！