Question

数据结构：迷宫求解（请高手指教--最好附上原代码及代码说明）

语言不限（分不多，大家别嫌弃）

Answer 1

#include<stdio.h>
#include<graphics.h>
#include<conio.h>

typedef struct{
int x,y;
int dir;
}pos,elem;

typedef struct{
elem* b,* t;
int size;
}stack;

void initstack(stack* s)
{
s->b=(elem*)malloc(50*sizeof(elem));
if(s->b){
s->t=s->b;
s->size=50;
return;
}
exit(0);
}
void push(stack* s,elem* e)
{
*s->t=*e;
s->t++;
}
void pop(stack* s,elem* e)
{
*e=*--s->t;
}
void gettop(stack* s,elem* e)
{
*e=*(s->t-1);
}
void clearstack(stack* s)
{
s->t=s->b;
}
int stackempty(stack* s)
{
return !(s->t-s->b);
}
int destroystack(stack* s)
{
free(s->b);
free(s);
return 1;
}
int mg[10][10]={
{-1,-0,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-0,-0,-0,-1,-0,-0,-0,-0,-1},
{-1,-0,-1,-0,-1,-0,-1,-1,-0,-1},
{-1,-0,-1,-1,-0,-0,-0,-0,-0,-1},
{-1,-0,-0,-1,-0,-1,-1,-0,-0,-1},
{-1,-0,-0,-0,-0,-0,-1,-0,-0,-1},
{-1,-0,-1,-0,-0,-0,-0,-1,-0,-1},
{-1,-0,-1,-1,-0,-0,-0,-1,-0,-1},
{-1,-0,-0,-0,-1,-0,-0,-1,-0,-0},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
};

void step(stack* s,pos* cur,stack* result);
void savepath(stack* s,pos* cur,stack* result);
void draw(int y,int x);

void step(stack* s,pos* cur,stack* result)
{
if(stackempty(result)||s->t-s->b<result->t-result->b){
for(cur->dir++;cur->dir<5;cur->dir++){
setfillstyle(SOLID_FILL,15);
switch(cur->dir){
case 1:
if(!mg[cur->y-1][cur->x]){
mg[cur->y][cur->x]=1;
push(s,cur);
cur->y--;
cur->dir=0;
draw(cur->y,cur->x);
return;
}
break;
case 2:
if(!mg[cur->y][cur->x+1]){
mg[cur->y][cur->x]=1;
push(s,cur);
cur->x++;
cur->dir=0;
draw(cur->y,cur->x);
return;
}
break;
case 3:
if(!mg[cur->y+1][cur->x]){
mg[cur->y][cur->x]=1;
push(s,cur);
cur->y++;
cur->dir=0;
draw(cur->y,cur->x);
return;
}
break;
case 4:
if(!mg[cur->y][cur->x-1]){
mg[cur->y][cur->x]=1;
push(s,cur);
cur->x--;
cur->dir=0;
draw(cur->y,cur->x);
return;
}
break;
default:
exit(0);
}
}
}
mg[cur->y][cur->x]=0;
setfillstyle(SOLID_FILL,0);
draw(cur->y,cur->x);
pop(s,cur);
}

void savepath(stack* s,pos* cur,stack* result)
{
pos* top=s->t;
if(stackempty(result)){
push(result,cur);
while(top>s->b)
push(result,--top);
}
else if(result->t-result->b>s->t-s->b){
clearstack(result);
push(result,cur);
while(top>s->b)
push(result,--top);
}
}

void draw(int y,int x)
{
bar(100+15*x,100+15*y,115+15*x,115+15*y);
}

void main(void)
{
int i;
int x,y;
int gd=DETECT,gm;
stack* s=NULL;
stack* result=NULL;
pos* cur=NULL;

initgraph(&gd,&gm,"");
for(x=0;x<10;x++)
for(y=0;y<10;y++){
if(mg[y][x]){
setfillstyle(SOLID_FILL,3);
draw(y,x);
}
}

result=(stack*)malloc(sizeof(stack));
initstack(result);
s=(stack*)malloc(sizeof(stack));
cur=(pos*)malloc(sizeof(pos));
initstack(s);
cur->x=1;
cur->y=0;
cur->dir=0;
push(s,cur);
cur->x=1;
cur->y=1;
cur->dir=1;
do{
if(cur->x==9&&cur->y==8)
savepath(s,cur,result);
step(s,cur,result);
}while(!stackempty(s));
if(stackempty(result))
printf("no way available");
else{
int ch=0;
printf("following is the shortest path:\n");
while(!stackempty(result)){
pop(result,cur);
setfillstyle(SOLID_FILL,15);
draw(cur->y,cur->x);
if(ch>5){
putchar('\n');
ch=0;
}
printf("(%d,%d,%d) ",cur->x,cur->y,cur->dir);
ch++;
}
}
printf("\n");
destroystack(s);
destroystack(result);
free(cur);
printf("Press any key to end");
while(!kbhit());
closegraph();
}