天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

走迷宫程序(应用栈)

Posted on 2012-02-28 00:37 hoshelly 阅读(656) 评论(0)  编辑 收藏 引用 所属分类: DS && Algorithm
//应用栈来走迷宫
#include<stdio.h>
#include<stdlib.h>
struct stack_node
{
    int x;//路径坐标x
    int y;//路径坐标y
    struct stack_node *next;//指向下一结点
};
typedef struct stack_node stack_list;
typedef stack_list *link;
link path=NULL;//路径栈指针
//栈数据的存入
link push(link stack,int x,int y)
{
    link new_node;//新结点指针
   
//分配结点内存
    new_node=(link)malloc(sizeof(stack_list));
    if(!new_node)
    {
        printf("内存分配失败!\n");
        return NULL;
    }
    new_node->x=x; //存入路径坐标x
    new_node->y=y; //存入路径坐标y
    new_node->next=stack;//新结点指向原开始
    stack=new_node; //新结点成为栈开始
    return stack;
}
//栈数据的取出
link pop(link stack,int *x,int *y)
{
    link top;//指向栈顶端
    if(stack!=NULL)
    {
        top=stack;
        stack=stack->next;//栈指针指向下结点
        *x=stack->x;//取出路径坐标x
        *y=stack->y;//取出路径坐标y
        free(top);
        return stack;
    }
    else
        *x=-1;
}
//主程序:用回溯的方法在数组迷宫找出口
//数字0:表示是可以走的路
//数字1:表示是墙壁,不可走的路
//数字2:表示是走过的路
//数字3:表示是回溯的路
void main()
{
    int maze[7][10]={
        1,1,1,1,1,1,1,1,1,1,
        1,0,1,0,1,0,0,0,0,1,
        1,0,1,0,1,0,1,1,0,1,
        1,0,1,0,1,1,1,0,0,1,
        1,0,1,0,0,0,0,0,1,1,
        1,0,0,0,1,1,1,0,0,1,
        1,1,1,1,1,1,1,1,1,1,};
    
    int i,j;
    int x=5;//迷宫入口坐标
    int y=8;
    while(x!=1||y!=1)//是否是迷宫出口
    {
        maze[x][y]=2;//标示走过的路
        if(maze[x-1][y]<=0) //往上方走
        {
            x=x-1;
            path=push(path,x,y);//存入路径
        }
        else if(maze[x+1][y]<=0)//往下方走
        {
                x=x+1;
                path=push(path,x,y);
        }
        else if(maze[x][y-1]<=0)//往左方走
        {
            y=y-1;
            path=push(path,x,y);
        }
        else if(maze[x][y+1]<=0)//往右方走
        {
            y=y+1;
            path=push(path,x,y);
        }
        else
        {
            maze[x][y]=3;
            path=pop(path,&x,&y);//退回一步
        }
    }
    maze[x][y]=2;
    printf("迷宫的路径如下图所示:\n");
    for(i=1;i<6;i++)//输出迷宫图形
    {
        for(j=1;j<9;j++)
            printf("%d",maze[i][j]);//输出各坐标
        printf("\n");
    }
}
        

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理