| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2870 人关注过本帖
标题:数据结构严蔚敏C语言版 迷宫问题求解
只看楼主 加入收藏
特仑苏
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2015-4-15
结帖率:0
收藏
已结贴  问题点数:20 回复次数:9 
数据结构严蔚敏C语言版 迷宫问题求解
#include<stdio.h>
#define r 64
#define m2 8
#define n2 10
int m=m2-2,n=n2-2;
typedef struct
{
    int x,y;    //行列坐标
    int pre;
}sqtype;

sqtype sq[r];
struct moved
{
    int x, y;  //坐标增量,取值-1,0,1
}move[8];

int maze[m2][n2];

int PATH(int maze[][n2])  //找迷宫maze的路径
{
    int i,j,k,v,front,rear,x,y;
    int mark[m2][n2];
    for(i=0;i<m2;i++)
        for(j=0;j<n2;j++)
            mark[i ][j]=0;
    printf("Please Input move array\n");
    for(i=0;i<8;i++)
    {
        scanf("%d,%d",&move[i ].x,&move[i ].y);
    sq[1].x=1;
    sq[1].y=1;
    sq[1].pre=0;
    front=1;
    rear=1;
    mark[1][1]=1;   //标记入口以到达过
    while(front<=rear)
    {
        x=sq[front].x;
        y=sq[front].y;    //(x,y)为出发点
        for(v=0;v<8;v++)  //搜索(x,y)的8个相邻(i,j)是否可以到达
        {
            i=x+move[v].x;
            j=y+move[v].y;
            if((maze[i ][j]==0)&&(mark[i ][j]==0))//(i,j)为可以到达点,将起入队
            {
                rear++;
                sq[rear].pre=front;
                mark[i ][j]=1; //标记(i,j)已经到达过
            }
            if((i==m)&&(j==n))    //到达出口
            {
                printf("THE PATH: \n");
                k=rear;
                do
                {
                    printf("(%d %d)<-",sq[k].x,sq[k].y);
                    k=sq[k].pre;//找前一点
                }while(k!=0);//k=0是已经到达
                for(i=1;i<19;i++)
                    printf("%3d",i);
                printf("\n");
                for(i=1;i<19;i++)
                    printf("%3d",sq[i ].x);
                printf("\n");
                for(i=1;i<19;i++)
                    printf("%3d",sq[i ].y);
                printf("\n");
                for(i=1;i<19;i++)
                    printf("%3d",sq[i ].pre);
                printf("\n");
                return(1);      //成功返回
            }
        }
        front++;   //出队,front 指向新的出发点
    }
    }
     //队空,循环结束
    printf("There is no path! \n");
    return(0);   //迷宫没有路径返回
}

main()
{
    int i,j;
    for(i=0;i<10;i++)
    {
        maze[0][i ]=1;
        maze[7][i ]=1;
    }
    for(i=0;i<8;i++)
    {
        maze[i ][0]=1;
        maze[i ][9]=1;
    }
    /*for(i=1;i<7;i++)
        for(j=1;j<9;j++)
        {
            printf("%d %d",i,j);
            scanf("%d",&maze[i ][j]);
        }*/   
    maze[1][1]=0;maze[1][2]=1;maze[1][3]=0;maze[1][4]=1;maze[1][5]=1;maze[1][6]=0;maze[1][7]=1;maze[1][8]=1;
    maze[2][1]=1;maze[2][2]=0;maze[2][3]=0;maze[2][4]=1;maze[2][5]=1;maze[2][6]=0;maze[2][7]=1;maze[2][8]=0;
    maze[3][1]=0;maze[3][2]=1;maze[3][3]=1;maze[3][4]=0;maze[3][5]=0;maze[3][6]=1;maze[3][7]=1;maze[3][8]=1;
    maze[4][1]=1;maze[4][2]=0;maze[4][3]=0;maze[4][4]=1;maze[4][5]=1;maze[4][6]=0;maze[3][7]=0;maze[4][8]=1;
    maze[5][1]=1;maze[5][2]=1;maze[5][3]=0;maze[5][4]=0;maze[5][5]=1;maze[5][6]=1;maze[5][7]=0;maze[5][8]=1;
    maze[6][1]=0;maze[6][2]=1;maze[6][3]=1;maze[6][4]=1;maze[6][5]=0;maze[6][6]=0;maze[6][7]=0;maze[6][8]=0;

    printf("\n");
    for(i=0;i<8;i++)
    {
        for(j=0;j<10;j++)
            printf("%d",maze[i ][j]);
        printf("\n");
    }
    PATH(maze);
}
搜索更多相关主题的帖子: C语言 include 
2015-10-29 08:34
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:20 
能说下你哪个地方出错了么?语法还是逻辑?
2015-10-29 10:03
特仑苏
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2015-4-15
收藏
得分:0 
回复 2楼 令狐少侠56
希望能够讲解一下思路

小小的天有大大的梦想
2015-11-06 08:59
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
回复 3楼 特仑苏
图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册

图片附件: 游客没有浏览图片的权限,请 登录注册
2015-11-06 22:06
特仑苏
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2015-4-15
收藏
得分:0 
能给说说这个数的名字吗?其实我想知道怎样去写需要用到的那些函数,一开始怎么就能先到用那些函数呢?

小小的天有大大的梦想
2015-11-16 22:46
令狐少侠56
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:320
专家分:175
注 册:2014-4-10
收藏
得分:0 
回复 5楼 特仑苏
书名叫《啊哈算法》推荐购买,还有学数据结构可以看看《大话数据结构》这本书还有mooc上的数据结构视频课程
2015-11-22 19:15
来生再见
Rank: 1
来 自:江西省抚州市
等 级:新手上路
威 望:1
帖 子:39
专家分:9
注 册:2015-9-13
收藏
得分:0 
程序代码:

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#define N 8

int  Maze[N + 2][N + 2];
int  MazeSigns[N + 2][N + 2];
int count = 0;
//坐标偏移量结构体 
typedef struct _Tag_Pos
{
    int xpos;
    int ypos;
}Pos;
//方向数组  顺序时针4个方向  上-->右-->下-->左
Pos pos[4] = { {-1,0}, {0,1}, {1,0}, {0,-1} };

//迷宫数组
void initMaze(void);
//迷宫标记数组
void initMazeSigns(void);
//设置迷宫和迷宫标记数组的障碍物
void setMaze(void);
//输出迷宫
void putMaze(void);
void putMazeSigns(void);
//搜索出路
void searchExiter(int x, int y,int dir);
int checkPos(int x, int y, int dir);

int main(int argc, char *argv[])
{
    initMaze();
    searchExiter(1, 1, 0);
    return 0;
}
//元素1表示障碍 元素0表示通道
void initMaze(void)
{
    //围墙一定是障碍
    for (int i = 0; i < N + 2;i++)
    {
        Maze[0][i] = 1;
        Maze[N+1][i] = 1;
        Maze[i][0] = 1;
        Maze[i][N+1] = 1;
    }

    for (int i = 1; i <= N;i++)
    {
        for (int j = 1; j <= N;j++)
        {    
            Maze[i][j] = 0;
        }
    }
    //设置迷宫内的障碍物
    setMaze();
    //设置迷宫标记数组
    initMazeSigns();

}

//标记数组 1代表不可通行 0代表可以通行 
//默认是不可通行的 1
void initMazeSigns(void)
{
    for (int i = 0; i < N+2; i++)
    {
        for (int j = 1; j < N+2; j++)
        {
            MazeSigns[i][j] = 1;
        }
    }
}
//设置迷宫的内的障碍 这个可以自己输入
void setMaze(void)
{
    Maze[1][3] = 1;
    Maze[1][7] = 1;
    Maze[2][3] = 1;
    Maze[2][7] = 1;
    Maze[3][5] = 1;
    Maze[3][6] = 1;
    Maze[4][2] = 1;
    Maze[4][3] = 1;
    Maze[4][4] = 1;
    Maze[5][4] = 1;
    Maze[6][2] = 1;
    Maze[6][6] = 1;
    Maze[7][2] = 1;
    Maze[7][3] = 1;
    Maze[7][4] = 1;
    Maze[7][6] = 1;
    Maze[7][7] = 1;
    Maze[8][1] = 1;
}
void putMaze(void)
{
    printf("count:%d\n", ++count);
    for (int i = 0; i < N+2; i++)
    {
        for (int j = 0; j < N+2; j++)
        {
            if (Maze[i][j] == 1)
            {
                printf(" #");
            }
            else if ((Maze[i][j] == -1) && (MazeSigns[i][j] == 0))
            {
                //Maze[i][j]==-1表示该位置在当前路径中
                printf(" *");
            }
            else if (Maze[i][j] == 0)
            {
                printf("  ");
            }
        }
        printf("\n");
    }
}

void putMazeSigns(void)
{
    for (int i = 0; i < N + 2; i++)
    {
        for (int j = 0; j < N + 2; j++)
        {
            printf("%2d", MazeSigns[i][j]);
        }
        printf("\n");
    }
}

//查找出口
//参数是才入口的坐标
/*
入口的坐标是:(1,1)
出口的坐标是:(8,8)
任何一个位置都有四个方向 顺序时针去遍历每个方向

1.从入口点位置 对4个方向顺序时针挨个检测活路
    a.某个方向有活路 就进入这个路口 重复步骤2
    b.某个方向没有活路 换下一个方向检测
    c.4个方向都检测了,表示这个迷宫没有出口
2.进入下个活路位置 对4个方向顺时针挨个进行活路检测
    a.某个方向有活路 就进入这个路口 重复步骤2 递归实现
    b.某个方向没有活路 换下一个方向检测
    c.4个方向都检测了,那么返回上一个路口 接着从下一个方向检测 回溯算法实现 
递归结束其实有2个情况:
一种是位置是(8,8)出口 这个时候表示找到出路了
一种是某个位置4个方向都是死路
*/
void searchExiter(int x, int y,int dir)
{
    if ((x==8) && (y==8))
    {
        //递归结束
        MazeSigns[x][y] = 0;
        Maze[x][y] = -1;
        putMaze();
        MazeSigns[x][y] = 1;
        Maze[x][y] = 0;
    }
    else
    {
        //只需要判断三个方向就好了
        for (int i = 0; i < 3;i++)
        {
            //下一位置起始方向
            dir = (++dir) % 4;
            //表示这个方向有活路
            if (checkPos(x, y, dir))
            {
                MazeSigns[x][y] = 0;//表示是通路
                Maze[x][y] = -1;//在路径中
                //寻找下一个位置
                int NextX = x + pos[dir].xpos;
                int NextY = y + pos[dir].ypos;
                searchExiter(NextX,NextY,(dir+2)%4);
                MazeSigns[x][y] = 1;//表示三条路上有部分路不通 
                Maze[x][y] = 0;//不在路径中
            }
        }
    }
}
//也就是检测当前位置k方向的位置是不是活路
int checkPos(int x, int y,int dir)
{
    //检测位置(x,y)的k方向的位置是不是活路
    int NextX = x + pos[dir].xpos;
    int NextY = y + pos[dir].ypos;
    return (Maze[NextX][NextY] == 0) ? 1 : 0;
}



迷宫 入口点是(1,1) 出口点是(8,8)
障碍物写死了

重新开始,努力
2015-11-30 00:09
特仑苏
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2015-4-15
收藏
得分:0 
回复 7楼 来生再见
棒棒哒,数据结构有毒,对女生来说就是有毒

小小的天有大大的梦想
2015-12-24 09:51
特仑苏
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2015-4-15
收藏
得分:0 
回复 7楼 来生再见
运行出问题了

小小的天有大大的梦想
2015-12-24 09:55
zhangdayin
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2016-2-25
收藏
得分:0 
有没有大体思想啊
2016-02-25 14:17
快速回复:数据结构严蔚敏C语言版 迷宫问题求解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.049171 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved