迷宫问题

发布时间:2016-12-11 4:30:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"迷宫问题",主要涉及到迷宫问题方面的内容,对于迷宫问题感兴趣的同学可以参考一下。

点击(此处)折叠或打开/* *题二:求解迷宫的一条最短路径,要求:用栈和队列实现, *不允许使用递归算法。问题描述见教材第50页“3.2.4 迷宫求解”。 */#include <stdio.h>#include <malloc.h>#include <conio.h>#define ERROR 0#define OK 1#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 100typedef struct {    int x;    int y;}PosType;typedef struct {    int ord;    PosType seat;    int di;}ElemType;typedef struct {    ElemType *base;    ElemType *top;    int stacksize;}SqStack;int InitStack (SqStack *S){    S->base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));    if (!S->base)         exit (OVERFLOW);    S->top=S->base;    S->stacksize=STACK_INIT_SIZE;    return OK;}int GetTop (SqStack S, ElemType *e){    if (S.top==S.base)        return ERROR;    *e=*(S.top-1);    return OK;}int Push (SqStack *S, ElemType e){    if (S->top - S->base >= S->stacksize)    {        S->base=(ElemType *)realloc(S->base,                              (S->stacksize + STACKINCREMENT)* sizeof(ElemType));        if (!S->base)            exit (OVERFLOW);        S->top=S->base+S->stacksize;        S->stacksize+=STACKINCREMENT;    }    *S->top++ = e;    return OK;}int Pop(SqStack *S,ElemType *e){    if (S->top==S->base)        return ERROR;    *e=*(--S->top);    return OK;}int StackEmpty (SqStack S){    if (S.base==S.top)        return 1;    else        return 0;}void ShowAll (SqStack *S){    ElemType t;    printf ("h l step\n");    while (1)    {        if (Pop (S, &t))        {            printf ("%d %d %d\n", t.seat.x, t.seat.y, t.ord);        }        else            break;    }}void Change (SqStack *From, SqStack *To) /* 逆置矩阵 */{    ElemType t;    while (1)    {        if (Pop (From, &t))            Push (To, t);        else            break;    }}int Pass(int maze[10][10], PosType local) /*当前位置是否可走*/{    if (maze[local.x][local.y]==1)        return 0;    else        return 1;}void FootPrint (int maze[10][10],PosType local)/*修改当前位置为1*/{    maze[local.x][local.y]=1;}PosType NextPos (PosType local ,int i){    if (i==1)    {        local.y+=1;    }    else if (i==2)    {        local.x+=1;    }    else if (i==3)    {        local.x-=1;    }    return local;}void MarkPrint (int maze[10][10],PosType local)/*修改当前位置为1*/{    maze[local.x][local.y]=1;}int MazePath (int maze[10][10],PosType start,PosType end,SqStack *S){    PosType local = start;    ElemType temp;    int step=1;    do {        if (Pass (maze, local))        {            FootPrint (maze, local);            temp.ord=step;            temp.seat=local;            temp.di=1;            Push (S,temp);            if (Equal(local, end))                return OK;            local = NextPos (local ,1);            step++;        }        else        {            if (!StackEmpty(*S))            {                Pop(S,&temp);                while (temp.di==4&&!StackEmpty(*S))                {                    MarkPrint (maze,temp.seat);                    Pop (S,&temp);                    step--;                }                if (temp.di<4)                {                    temp.di++;                    Push (S,temp);                    local=NextPos(temp.seat, temp.di);               }            }        }     }while (!StackEmpty (*S));     return ERROR;}int Equal (PosType A,PosType B){    if (A.x==B.x&&A.y==B.y)        return 1;    else        return 0;}int main (){    PosType start,end;    SqStack s;    int result=0;    int maze [10][10] =    { {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}};    start.x=1;    start.y=1;    end.x=8;    end.y=8;    InitStack (&s);    result=MazePath (maze, start, end, &s);    if (result)    {        printf ("found\n");        ShowAll(&s);    }    else        printf ("not found");    getchar();    return 0;} 管理员在2009年8月13日编辑了该文章文章。 --> --> 阅读(483) | 评论(0) | 转发(0) | 0 上一篇:栈的应用 下一篇:稀疏矩阵的存储与快速转置 相关热门文章 建筑工程管理软件信息管理的目... 罗一平:建设美术馆的理想并未... 工作狂如何调整自己 测试你的内心是否脆弱... 澳洲文凭损坏,致远补办,加拿... test123 编写安全代码——小心有符号数... 使用openssl api进行加密解密... 一段自己打印自己的c程序... sql relay的c++接口 怎么样找出BIND中查询并发量多... 可有人在实际的openstack生产... 如下makefile如何编写 sqlldr 参数配置 讨论一下各位所管理的mysql生... 热门推荐 --> 给主人留下些什么吧!~~ 评论热议

上一篇:认识ASP.NET会话状态
下一篇:稀疏矩阵的存储与快速转置

相关文章

关键词: 迷宫问题

相关评论