关于迷宫的算法求解问题 - 数据结构与算法

得分:4

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 10000
#define STACKINCREMENT 100
#define M 10
#define N 10
int flag=0;
typedef struct//坐标位置
{
    int x;
    int y;
}PosType;
typedef struct//栈中元素结构体
{
    int ord;//序号
    PosType seat;//坐标位置
    int di;//通道方向(1东2南3西4北)
}SElemType;
typedef struct//栈
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;
////////////////////////////////////////栈操作
void initialStack(SqStack *s)
{
    s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!s->base) exit(0);
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,SElemType e)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(SElemType *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
        if(!s->base) exit(0);
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
    }
    (*(s->top)).ord=e.ord;
    (*(s->top)).seat.x=e.seat.x;
    (*(s->top)).seat.y=e.seat.y;
    (*(s->top)).di=e.di;
    s->top++;
}
void Pop(SqStack *s,SElemType *e)
{
    if(s->top==s->base) exit(0);
    (s->top)--;
    e->ord=(*(s->top)).ord;
    e->seat.x=(*(s->top)).seat.x;
    e->seat.y=(*(s->top)).seat.y;
    e->di=(*(s->top)).di;
}
int StackEmpty(SqStack *s)
{
    if(s->top==s->base) return(1);
    else return(0);
}
void ClearStack(SqStack *s)
{
    s->top=s->base;
    s->stacksize=0;
}
//////////////////////////////////////////初始化迷宫
void initialarray(int (*p)[N])
{
    int i,j;
    int maze[M][N]={1,1,1,1,1,1,1,1,1,1,
                    1,0,0,1,0,0,0,1,0,1,
                    1,0,0,0,0,1,0,1,0,1,
                    1,0,0,1,1,0,0,0,0,1,
                    1,1,1,1,1,0,0,1,0,1,
                    1,0,0,0,1,0,0,0,0,1,
                    1,0,1,0,0,1,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};/***/
    printf("打印迷宫:\n");
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
        {
            printf("%d",maze[i][j]);
            *(*(p+i)+j)=maze[i][j];/***/
        }
        printf("\n");
    }
}
///////////
void NextPos(PosType *p,int d)//确定下一个位置的坐标
{
    switch(d)
    {
    case 1:p->y++;break;
    case 2:p->x++;break;
    case 3:p->y--;break;
    case 4:p->x--;break;
    }    /////////////////////////(1东2南3西4北)改变坐标
}
void MazePath(int (*maze)[N])//核心函数//---int (*maze)[N]
{
    int curstep;
    int mark[M][N]={0};
    SqStack s;
    PosType curpos;
    SElemType e;//栈中元素结构体 1.序号;2.坐标位置;3.通道方向
    initialStack(&s);
    curpos.x=1;
    curpos.y=1;
    curstep=1;
    do
    {
        if((!maze[curpos.x][curpos.y])&&(!mark[curpos.x][curpos.y]))//*******
        {
            mark[curpos.x][curpos.y]=1;
            e.ord=curstep;//**e=(curstep,curpos,1)
            e.seat.x=curpos.x;
            e.seat.y=curpos.y;
            e.di=1;//***
            Push(&s,e);
            if((curpos.x==M-2)&&(curpos.y==N-2))
            {

                flag=1;
                printf("走出迷宫的一条坐标路径为:\n[终点]");
                while(!StackEmpty(&s))
                {
                    Pop(&s,&e);
                    printf("<--(%d,%d)",e.seat.x,e.seat.y);
                }
                printf("<--[起点]");
                printf("\n");
                ClearStack(&s);
            }
                NextPos(&curpos,1);//curpos=NextPos(curpos,1)
                curstep++;
        }
            else
            {
                if(!StackEmpty(&s))
                    Pop(&s,&e);
                while(e.di==4&&!StackEmpty(&s))
                {
                    mark[e.seat.x][e.seat.y]=1;
                    Pop(&s,&e);
                }
                if(e.di<4)
                {
                    e.di++;
                    Push(&s,e);
                    curpos.x=e.seat.x;//**curpos=NextPos(e.seat,e,di)
                    curpos.y=e.seat.y;
                    NextPos(&curpos,e.di);///**
                }
            }
    }while(!StackEmpty(&s));
}
void main()
{
    int array[M][N];
    initialarray(array);
    MazePath(array);
    if(flag==0)
        printf("该迷宫不能走出去!\n");
}