百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

C语言数据结构实现:迷宫问题的通用解法

yuyutoo 2024-10-23 16:43 5 浏览 0 评论

问题:

以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

基本要求

输入的形式和范围:

非递归:行列为整型,坐标为整型

递归:迷宫以整型二维数组形式输入

输出的形式:非递归输出三元组通路和方阵通路;

递归以方阵输出迷宫和所有通路;

1、非递归算法,求一条通路输出三元组形式如:(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),…和方阵通路;

2、递归算法,求得迷宫中所有可能的通路,以方阵形式输出迷宫及其通路。

递归解法:

#include <stdio.h>
#include <malloc.h>
#define M 6
#define N 6
#define END N-2
int flag=0;
typedef struct
{
    int x,y,d;
}position;

/*创建迷宫*/
void creat_maze(int a[][M])
{
    int i,j;
    for(i=0;i<=N-1;i++)
        for(j=0;j<=M-1;j++)
        scanf("%1d",&a[i][j]);
}

position nextq(int maze[][M],position q)
{
    if(q.d==0)
        q.y++;
    else if(q.d==1)
        q.x++;
    else if(q.d==2)
        q.y--;
    else if(q.d==3)
        q.x--;
    return q;
}
void initialmat(int route[][M])       //初始化输出路径图
{
    int i,j;
    for(i=0;i<N;i++)
        for(j=0;j<M;j++)
            route[i][j]=1;
}
void print_maze(int mat[][M])        //输出迷宫
{
    int i,j;
    for(i=0;i<N;i++)
        {
        for(j=0;j<M;j++)
           printf("%d ",mat[i][j]);
           printf("\n");
        }

}
void MazePath(int maze[][M],int route[][M],position ps)
{
    position q;
    route[ps.x][ps.y]=0;
    maze[ps.x][ps.y]=-1;
    q=nextq(maze,ps);
    q.d=0;
    if(q.x==END&&q.y==END)
    {
        flag++;
        printf("\n第%d条路:\n",flag);
        route[END][END]=0;
        print_maze(route);
        route[END][END]=1;
    }
    else if(maze[q.x][q.y]==0)
        MazePath(maze,route,q);
    if(ps.d<=3)
    {
        ps.d++;
        MazePath(maze,route,ps);
    }
    route[ps.x][ps.y]=1;
    maze[ps.x][ps.y]=0;
}
void main()
{
    int maze[N][M],route[N][M];
    position ps;
    ps.x=ps.y=1;
    ps.d=0;
    printf("输入一个迷宫(%d*%d):\n",N,M);
    creat_maze(maze);
    printf("\n输出该迷宫:\n");
    print_maze(maze);
    printf("输出从(1,1)到(%d,%d)的所有通路:\n",N-2,M-2);
    initialmat(route);
    MazePath(maze,route,ps);
}

非递归解法:

#include<stdio.h>
#include<stdlib.h>
#define Elemtype int
#define MAXSIZE 50
typedef struct
{
    int x,y;
}mark;               //起点、终点坐标

typedef struct
{
    Elemtype x,y;    //迷宫数组坐标(x,y)
    int d;    //下一步的方向
}TriMatrix;

typedef struct LStackNode
{
    TriMatrix elem;
    struct LStackNode *next;
}LStack,*PLStack;

//栈的基本操作

PLStack InitStack(PLStack S)
{
    S=NULL;
	return S;
}

int StackEmpty(PLStack S)
{
    if(S==NULL)  return 1;
    else return 0;
}

PLStack Push(PLStack S,TriMatrix e)   //入栈
{
    PLStack P;
    P=(PLStack)malloc(sizeof(LStack));
    P->elem=e;
    P->next=S;
    S=P;
	return S;
}

PLStack Delete(PLStack S)   //删除栈头
{
    PLStack P;
    P=S;
	if(!StackEmpty(S))
	{
        S=S->next;
        free(P);
        return S;
	}
}

TriMatrix Pop(PLStack S,TriMatrix e)  //出栈
{
    if(!StackEmpty(S))
	{
        e=S->elem;
        return e;
	}
}

void MazePath(mark start,mark end,
              Elemtype maze[MAXSIZE][MAXSIZE],
              int m,int n,int diradd[4][2])   //寻找路径
{
    int i,j,d;
    int a,b;
    TriMatrix elem,e;
    PLStack S1,S2;
    S1=InitStack(S1);
    S2=InitStack(S2);
    maze[start.x][start.y]=2;   //修改入口坐标,做标记
    elem.x=start.x;
    elem.y=start.y;
    elem.d=0;  //开始为0
    S1=Push(S1,elem);
    while(!StackEmpty(S1))  //栈不空,有路可走
    {
        elem=Pop(S1,elem);
		S1=Delete(S1);
        i=elem.x;
        j=elem.y;
        d=elem.d+1;
        while(d<=4)
        {
            a=i+diradd[d-1][0];
            b=j+diradd[d-1][1];
            if(a==end.x&&b==end.y&&maze[a][b]==0)  //出口
            {
                elem.x=i;
                elem.y=j;
                elem.d=d;
                S1=Push(S1,elem);
                elem.x=a;
                elem.y=b;
                elem.d=0;   //方向输出为0,判断是否为出口
                S1=Push(S1,elem);
                printf("\n1=东 2=南 3=西 4=北 0为走出迷宫\n\n路径为:(行坐标,列坐标,方向)\n");
                while(S1)  //逆置序列 并输出路径
                {
                    e=Pop(S1,e);
					S1=Delete(S1);
                    S2=Push(S2,e);
                }
                while(S2)
                {
                    e=Pop(S2,e);
					S2=Delete(S2);
                    printf("-->(%d,%d,%d)",e.x,e.y,e.d);maze[e.x][e.y]=3;
                }
				printf("\n\n");
				for(i=0;i<=m+1;i++){
                for(j=0;j<=n+1;j++)
                    if(maze[i][j]==3) printf("0 ");
                    else printf("1 ");
                    printf("\n");
                }
                return;
            }//if
            if(maze[a][b]==0)
            {
                maze[a][b]=2;
                elem.x=i;
                elem.y=j;
                elem.d=d;
                S1=Push(S1,elem);
                i=a;  j=b;  d=0;
            }
            d++;
        }
    }
    printf("没有出迷宫的路径\n");
}

//建立迷宫
void initmaze(int maze[MAXSIZE][MAXSIZE],int m,int n)
{
    int i,j;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
        maze[i][j]=rand()%2;
    for(i=0;i<=m+1;i++)
    {
        maze[i][0]=maze[i][n+1]=1;
    }
    for(j=0;j<=n+1;j++)
    {
        maze[0][j]=maze[m+1][j]=1;
    }
    printf("输出迷宫:\n");
    for(i=0;i<=m+1;i++)
    {
        for(j=0;j<=n+1;j++)
        printf("%d ",maze[i][j]);
        printf("\n");
    }
}

void main()
{
    int maze[MAXSIZE][MAXSIZE];
    mark start,end;
    int m,n;  //迷宫行列
    printf("输入迷宫的行数m和列数n:\n");
    scanf("%d%d",&m,&n);
    int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    initmaze(maze,m,n);
    printf("输入入口坐标和出口坐标:\n");
    scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);
    MazePath(start,end,maze,m,n,add);
}

写在最后:对于准备学习C/C++编程的小伙伴,如果你想更好的提升你的编程核心能力(内功)不妨从现在开始!

编程学习书籍分享:

编程学习视频分享:

整理分享(多年学习的源码、项目实战视频、项目笔记,基础入门教程)

欢迎转行和学习编程的伙伴,利用更多的资料学习成长比自己琢磨更快哦!

对于C/C++感兴趣可以关注小编在后台私信我:【编程交流】一起来学习哦!可以领取一些C/C++的项目学习视频资料哦!已经设置好了关键词自动回复,自动领取就好了!

相关推荐

野路子科技!2步教你把手机改造成一个FTP服务器,支持PC互传

哈喽,大家好,我是野路子科技,今天来给大家带来一个教程,希望大家喜欢。正如标题所言,就是教大家如何把售价改造成FTP服务器,而这个时候估计有朋友会问了,把手机改造成FTP服务器有什么用呢?现在有Q...

不得不看:别样于Server-U的群晖文件存储服务器的搭建与使用

我先前的作品中,有着关于Server-U的ftp文件存储服务器的搭建与访问的头条文章和西瓜视频,而且我们通过各种方式也给各位粉丝介绍了如何突破局域网实现真正意义上的公网访问机制技术。关于Server-...

Qt三种方式实现FTP上传功能_qt引入qftp库

FTP协议FTP的中文名称是“文件传输协议”,是FileTransferProtocol三个英文单词的缩写。FTP协议是TCP/IP协议组中的协议之一,其传输效率非常高,在网络上传输大的文件时,经...

Filezilla文件服务器搭建及客户端的使用

FileZilla是一个免费开源的FTP软件,分为客户端版本和服务器版本,具备所有的FTP软件功能。可控性、有条理的界面和管理多站点的简化方式使得Filezilla客户端版成为一个方便高效的FTP客户...

美能达柯美/震旦复印机FTP扫描怎么设置?

好多网友不知道怎么安装美能达/震旦复印机扫描,用得最多是SMB和FTP扫描,相对于SMB来说,FTP扫描安装步骤更为便捷,不容易出问题,不需要设置文件夹共享,所以小编推荐FTP来扫描以美能达机器为例详...

CCD(简易FTP服务器软件)_简单ftp服务器软件

CCD简易FTP服务器软件是一款很方便的FPT搭建工具,可以将我们的电脑快速变成一个FPT服务器。使用方法非常简单,只要运行软件就会自动生效,下载银行有该资源。该工具是不提供操作界面的,其他用户可以输...

Ubuntu系统搭建FTP服务器教程_ubuntu架设服务器

在Ubuntu系统上搭建FTP服务器是文件传输的一个非常实用方法,适合需要进行大量文件交换的场景。以下是一步步指导,帮助您在Ubuntu上成功搭建FTP服务器。1.安装vsftpd软件...

理光FTP扫描设置教程_理光ftp扫描设置方法

此教程主要用来解决WIN10系统下不能使用SMB文件夹扫描的问题,由于旧的SMB协议存在安全漏洞,所以微软在新的系统,WIN8/WIN10/SERVER201220162018里使用了新的SMB传...

纯小白如何利用wireshark学习网络技术

写在前面工欲善其事必先利其器!熟悉掌握一种神器对以后的工作必然是有帮助的,下面我将从简单的描述Wireshark的使用和自己思考去写,若有错误或不足还请批评指正。...

京东买13盘位32GB内存NAS:NAS系统安装设置教程

本内容来源于@什么值得买APP,观点仅代表作者本人|作者:yasden你没有看错,我在京东自营商城购买硬件,组装了一台13盘位,32GB内存的NAS,硬盘有13个盘位!CPU是AMD的5500!本文...

FileZilla搭建FTP服务器图解教程_filezilla server搭建ftp服务器

...

python教程之FTP相关操作_python ftps

ftplib类库常用相关操作importftplibftp=ftplib.FTP()ftp.set_debuglevel(2)#打开调试级别2,显示详细信息ftp.connect(“I...

xftp怎么用,xftp怎么用,具体使用方法

Xftp是一款界面化的ftp传输工具,用起来方便简单,这里为大家分享下Xftp怎么使用?希望能帮到有需要的朋友。IIS7服务器管理工具可以批量管理、定时上传下载、同步操作、数据备份、到期提醒、自动更新...

树莓派文件上传和下载,详细步骤设置FTP服务器

在本指南中,详细记录了如何在树莓Pi上设置FTP。设置FTP可以在网络上轻松地将文件传输到Pi上。FTP是文件传输协议的缩写,只是一种通过网络在两个设备之间传输文件的方法。还有一种额外的方法,你可以用...

win10电脑操作系统,怎么设置FTP?windows10系统设置FTP操作方法

打印,打印,扫描的日常操作是每一个办公工作人员的必需专业技能,要应用FTP作用扫描文件到电脑上,最先要必须一台可以接受文件的FTP服务器。许多软件都需要收费标准进行,但人们还可以应用Windows的系...

取消回复欢迎 发表评论: