#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>

#define SIZE 100;
#define ADD 10;
typedef struct node1 {
    int x;
    int y;
}positype;
typedef struct node2 {
    int step;
    positype seat;
    int di;
}statype,*staptr;
typedef struct node3 {
    staptr base;
    staptr top;
    int size;
}sqsttype;

void initstack(sqsttype &p)
{
    staptr s;
    s=(staptr)malloc(SIZE*(sizeof(statype)));
    if(!s) exit(-1);
    p.base=p.top=s;
    p.size=100;
}
void pushsta(sqsttype &p,statype e)
{
    if(p.top-p.base>=p.size)
    {
        p.base=(staptr)realloc(p.base,(p.SIZE+ADD)*sizeof(statype));
        if (!p.base) exit(-1);
        p.top=p.base+p.size;
        p.size+=ADD;
    }
    p.top++;
    p.top=e;
}
void pop(sqsttype &p,statype &e)
{
    if (p.top==p.base) exit(-1);
    e=p.top;
    p.top--;
}
int emptyst(sqsttype p)
{
    if(p.top==p.base)
    return 1;
    else return 0;
}
statype create(int step,positype curpos,int di)
{
    statype e;
    e.step=step;e.seat=curpos;e.di=di;
    return e;
}
int pass(int a[m],positype curpos)
{
    return(a[curpos.y][curpos.x]==0||a[curpos.y][curpos.x]==3||a[curpos.y][curpos.x]==4);
}
void footprint(int &a[m],positype curpos)
{
    a[curpos.y][curpos.x]=='*';
}
void makprint(int &a[m],positype e.seat)
{
    a[curpos.y][curpos.x]='$';
}
void creatmaze(int &a[m],int m,int n,positype &enter,positype &out)
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",a[i][j]);
            if(a[i][j]==3)
            {
                enter.x=j;
                emter.y=i;
            }
            if(a[i][j]==4)
            {
                out.x=j;
                out.y=i;
            }
        }
    }

}
positype nextcurp(positype curpos,int di)
{
    positype pos=curpos;
    switch(di)
    {
        case 1://南
            pos.y++;
            break;
        case 2:
            pos.x--;
            break;
        case 3:
            pos.y--;
            break;
        case 4:
            pos.x++;
            break;
        return pos;
    }

}
void mazepath(sqsttype &p,int &a[m],positype &enter,positype &out)
{
    positype curpos;
    curpos=enter;
    initstack(p);
    int step=1;
    do
    {
        if(pass(a[m],curpos))
        {
            footprint(a[m],curpos);
            e=create(step,curpos,1);
            pushsta(p,e);
            if(curpos.x=out.x&&curpos.y==out.y) return 1;
            curpos=nextcurp(curpos,1);
            step++;
        }
        else
        {
            if(!emptyst(p))
            pop(p,e);
            while(e.di==4&&!emptyst(p))
            {
                markprint(a[m],e.seat);
                step--;
            }
            if(e.di<4)
            {
                e.di++;pushsta(p,e);
                curpos=nextcurp(e.seat,e.di);
            }
        }
    }while(!emptyst(p));
    return 0;
}
void mazeprint(sqsttype &p)
{
    while(!emptyst(p))
    {
        pop(p,e);
        printf("%d %d\n",e.seat->x,e.seat->y);
    }
}
int main()
{
    int m,n;
    staptr p;
    scanf("%d%d",&m,&n);
    int a[m][n];
    positype enter,out;
    creatmaze(a[m],m,n,enter,out);
    if(mazepath())
    pathprint(p);
    else
    printf("没找到通路");
    return 0;
}
描述：    迷宫问题
   
    迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径.
输入：    迷宫宽度w 迷宫高度h
    迷宫第一行
    迷宫第二行
    ...
    迷宫第h 行
输出：    入口横坐标1  入口纵坐标1
    横坐标2       纵坐标2
    横坐标3       纵坐标3
    横坐标4       纵坐标4
    ...
    横坐标n-1    纵坐标n-1
    出口横坐标n 出口纵坐标n
输入样例：    8 10
    1 1 1 1 1 1 1 1
    1 0 1 1 0 1 0 1
    1 0 1 0 0 1 0 1
    1 1 0 3 1 0 1 1
    1 0 0 1 0 0 4 1
    1 0 0 0 0 1 1 1
    1 0 1 0 0 1 0 1
    1 0 1 0 0 0 1 1
    1 1 1 1 0 0 0 1
    1 1 1 1 1 1 1 1
输出样例：   
    3 3
    2 3
    2 4
    2 5
    3 5
    3 6
    3 7
    4 7
    4 6
    4 5
    4 4
    5 4
    6 4


[ 本帖最后由 维海 于 2011-3-27 18:16 编辑 ]

看我的吧   

谢谢

很不错啊

呵呵   大家谁会图片压缩  帮我去看一个我发的帖子   100分的哦