`

迷宫求解

阅读更多
采用了以栈为基础,在栈的基础上进行迷宫的求解,用Stack和Maze两个文件来实现功能。

Stack.h的实现如下:
#pragma once

#include <stdio.h> 
#include <malloc.h> 
#include <stdlib.h> 
#include <string.h>
typedef int DirectiveType;        //下一个通道方向 
#define RANGE 100                 //迷宫大小 
#define STACK_INIT_SIZE 100
#define STACKINCREMENT    10
//------------  栈的顺序存储实现  ------------------------------
typedef struct
{
int row;                     //迷宫中的行
    int col;                     //迷宫中的列
}PosType;                        //坐标(row,col)

typedef struct
{
    int step;                    //当前位置在路径上的"序号"
    PosType seat;                //当前的坐标位置
    DirectiveType di;            //往下一个坐标位置的方向
}SElemType;                      //栈的元素类型
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

bool InitStack(SqStack &s);          //栈的创建,即构造一个空栈
bool GetTop(SqStack s,SElemType &e); //如栈不为空,用e返回栈顶元素
bool Push(SqStack &s, SElemType e);  //在栈中插入元素
bool Pop(SqStack &s, SElemType &e);  //删除栈顶元素
bool StackEmpty(SqStack s);          //判断栈为不为空
bool DestoryStack(SqStack &s);       //销毁栈

Stack.cpp实现如下:
#include "Stack.h"              
#include "Maze.h"   

bool InitStack(SqStack &s)
{ //栈的初始化
    s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!s.base)
{
exit(-2);
}
    s.top=s.base;
    s.stacksize=STACK_INIT_SIZE;
    return true;
}

bool GetTop(SqStack s, SElemType &e )
{
    if( s.top == s.base)
{
return false;
}
    e = *(s.top-1);
    return true;
}

bool Push(SqStack &s, SElemType e)
{
    if(s.top-s.base >= s.stacksize)
{    //栈满,追加存储空间
        s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!s.base)
{
exit(-2);
}
        s.top = s.base + s.stacksize;
        s.stacksize += STACKINCREMENT;
    }
    *s.top++ = e;
    return true;
}

bool Pop(SqStack &s, SElemType &e)
{
    if(s.top==s.base)
return false;
    e = * --s.top;
    return true;
}

bool StackEmpty(SqStack s)
{
    return s.base == s.top;
}

bool DestoryStack(SqStack &s)
{
free(&s);
return true;
}


Maze.h实现如下:
typedef int DirectiveType;        //下一个通道方向 
#define RANGE 100                 //迷宫大小 
#define ROW 10                    //迷宫的行数
#define COL 10                    //迷宫的列数   
typedef struct
{
    int m,n;
    int arr[RANGE][RANGE];
}MazeType;  
  
bool InitMaze(MazeType &maze, int a[ROW][COL], int row, int col);//初始化迷宫
bool Pass(MazeType maze,PosType curpos);                         //判断能否通过
bool FootPrint(MazeType &maze,PosType curpos);                   //留下足迹
bool MarkPrint(MazeType &maze,PosType curpos);                   //留下不能通过的标记
PosType NextPos(PosType curpos, DirectiveType di);               //curpos当前位置
                                                                 //返回当前节点的下一节点
bool PosEqual(PosType pos1, PosType pos2);                       //判断两节点是否相等
void PrintMaze(MazeType maze,int row,int col);
bool MazePath(MazeType &maze,PosType start, PosType end);        //求解一条路径

Maze.cpp实现如下:
#include "Stack.h"              
#include "Maze.h"   

bool InitMaze(MazeType &maze, int a[ROW][COL], int row, int col)
{
int i,j;//设置迷宫maze的初值,包括加上边缘一圈的值
    for(i=1;i<row-1;i++)
{
        for(j=1;j<col-1;j++)
{
            maze.arr[j] = a[j];
        }
    }
    //加上围墙
    for(j=0;j<row;j++)
{
        maze.arr[0][j] = maze.arr[row-1][j]=1;
    }
    for(i=0;i<col;i++)
{
        maze.arr[0] = maze.arr[col-1]=1;
    }
    return true;
}

bool Pass(MazeType maze,PosType curpos)
{ //判断当前节点是否通过
    if(maze.arr[curpos.row][curpos.col] == 0)
{
return true;
}
else
{
return false;
}
}

bool FootPrint(MazeType &maze,PosType curpos)
{ //留下足迹
    maze.arr[curpos.row][curpos.col]=2;//走过且走得通
    return true;
}

bool MarkPrint(MazeType &maze,PosType curpos)
{//留下不能通过的标记
    maze.arr[curpos.row][curpos.col]=3;  //走过但走不通
    return true;
}

SElemType CreateSElem(int step, PosType pos, int di)
{  
    SElemType e;
    e.step = step;
    e.seat = pos;
    e.di = di;
    return e;
}

PosType NextPos(PosType curpos, DirectiveType di)//curpos当前位置
{//返回当前节点的下一节点
    PosType pos = curpos;
    switch(di)
    {
    case 1:        //右
        pos.col++;
        break;
    case 2:        //下
        pos.row++;
        break;
    case 3:        //左
        pos.col--;
        break;
    case 4:        //上
        pos.row--;
        break;
    }
    return pos;
}

bool PosEqual(PosType pos1, PosType pos2)
{//判断是不是出口
    if(pos1.row==pos2.row && pos1.col==pos2.col)
{
return true;
}
else
{
return false;
}
}

void PrintMaze(MazeType maze,int row,int col)
{//打印路径
int i,j;
printf("   ");
for(i=0;i<col;i++)//打印列数名
{
printf("%d ",i);
}
printf("\n");
for(i=0;i<row;i++)
{
printf("%d  ",i);//打印行数名
        for(j=0;j<col;j++)
{
            switch(maze.arr[j])
{
            case 0:
                printf("  ");//没走过,但是通路
                break;
case 1:
                printf("# ");//障碍
                break;
            case 2:
                printf("* ");//走过且走得通
                break;
            case 3:
                printf("@ ");//走过但走不通
                break;
    default:
break;
}     
        }
printf("\n");
    }
}

bool MazePath(MazeType &maze, PosType start, PosType end)
{ //求解迷宫maze中,从入口start到出口end的一条路径
    SqStack s;
SElemType e;
    InitStack(s);
    PosType curpos = start;
    int curstep = 1;                              //探索第一步
    do{
        if( Pass(maze,curpos) )
{    //如果当前位置可以通过,即是未曾走到的通道块
            FootPrint(maze,curpos);               //留下足迹
            e = CreateSElem(curstep,curpos,1);    //创建元素
            Push(s,e);
            if( PosEqual(curpos,end) )  
{
return true;
}
            curpos=NextPos(curpos,1);             //获得下一节点
            curstep++;                            //探索下一步
        }
else{                                     //当前位置不能通过
            if(!StackEmpty(s))
{
                Pop(s,e);
while(e.di==4 && !StackEmpty(s) ) //找寻了四个方向
{
                    MarkPrint(maze,e.seat);
Pop(s,e);                     //留下不能通过的标记,并退回一步
                }
if(e.di<4)
{
                    e.di++;                       //换一个方向探索
Push(s,e);           
                    curpos = NextPos(e.seat,e.di); //设定当前位置是该方向上的相邻块
                }

               
            }
        }
    }while(!StackEmpty(s));
    return false;
}


主测试函数如下:
#include "Stack.h"              
#include "Maze.h" 
        
void main()
{
char cmd;//命令
int i,j;
PosType start,end;
MazeType maze;
    int a[ROW][COL] = {
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,0,0,1},
{1,0,0,1,1,1,0,0,1,1},
{1,1,0,0,0,0,0,0,1,1},
{1,1,0,1,1,1,1,0,1,1},
{1,1,0,0,1,1,1,0,1,1},
{1,1,1,0,1,1,1,0,0,1},
{1,1,1,0,0,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
printf("\n----------原始迷宫(加外围围墙)(0 表示通路,1 表示障碍)---------\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ",a[j]);
}
printf("\n");
}
    InitMaze(maze,a,ROW,COL);
do{
int flag=0;//是不是越界de标志。0即没越界执行下一步,1即循环再次输入
do{
printf("\n输入迷宫入口坐标( <0,0>到<9,9>之间 ): ");
scanf("%d,%d",&start.row,&start.col);
if(start.col>COL-1 || start.row>ROW-1 ||start.col<0||start.row<0)
{
printf("越界!");
flag=1;
}
else
{
flag=0;
}
}while(flag);
do{
printf("输入迷宫出口坐标( <0,0>到<9,9>之间 ): ");
scanf("%d,%d",&end.row , &end.col);
if( end.col>COL-1 || end.row>ROW-1 ||end.col<0||end.row<0)
{
printf("越界!\n");
flag=1;
}
else
{
flag=0;
}
}while(flag);
if(MazePath(maze,start,end))//找到一条路径
{
printf("\n---------从当前入口到出口有通路 * 组成的路径----------\n");
PrintMaze(maze,ROW,COL);
}
else
{
printf("\n---------从入口到出口没有通路!-----\n");
}
printf("\n 需要继续吗?: ");
scanf(" %c",&cmd);
}while(cmd=='Y'||cmd=='y');
}
源码来自 算法源码:http://www.eyesourcecode.com/forum-algorithm-1.html


  • 大小: 11.9 KB
1
1
分享到:
评论

相关推荐

    课程设计之迷宫求解问题

    在本课程设计中,我们将深入探讨迷宫求解这一经典问题。迷宫求解是计算机科学中的一个重要领域,它涉及到图论、算法设计与分析等多个方面。在这个项目中,我们将学习如何利用不同的方法来解决这类问题,从而提高我们...

    数据结构(C语言版)迷宫求解问题

    本话题聚焦于一个经典的问题——“迷宫求解”,通过C语言实现,利用非递归和栈操作的方法来找到迷宫的出路。让我们深入探讨这个话题。 首先,迷宫求解问题是一个典型的图遍历问题,可以抽象为一个二维网格,每个...

    迷宫求解MFC代码

    在本文中,我们将深入探讨如何使用Microsoft Foundation Classes (MFC) 框架来实现一个迷宫求解的程序。MFC是微软为Windows应用程序开发提供的一种C++库,它简化了Win32 API的使用,使开发者能够更加专注于应用程序...

    迷宫求解的代码

    在IT领域,迷宫求解是一个经典的问题,它涉及到图论、算法和数据结构等多个方面的知识。本主题的核心是设计一个程序,能够找到从迷宫的起点(入口)到终点(出口)的一条可行路径。这里我们将深入探讨迷宫求解的原理...

    迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解

    迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解...

    迷宫求解课程设计报告完整版

    【迷宫求解课程设计】是计算机科学领域中常见的一个问题,通常用于教授基本的图论概念和搜索算法。在这个课程设计中,目标是设计一个C++程序,解决一个8x8的迷宫问题,从入口(1,1)找到所有可能路径及最短路径至出口...

    迷宫求解算法数据结构c语言

    从给定的代码片段和描述来看,这是一段用C语言实现的迷宫求解算法,涉及到了数据结构中的栈的应用。接下来,我们将详细解析这段代码所体现的关键知识点。 ### 迷宫求解算法 迷宫求解算法通常采用深度优先搜索(DFS...

    迷宫求解源代码

    vc++编写的迷宫求解程序 课程名称:数据结构课程设计(A) 课程编号:L11008 一、 实现功能: 输入迷宫的行数(假设为M)和列数(假设是N),单击创建迷宫按钮,随机生成一个M行N列的迷宫,单击显示路径按钮,如果...

    c++迷宫求解程序

    在编程领域,迷宫求解是一个经典的问题,它涉及到图论、深度优先搜索(DFS)或广度优先搜索(BFS)等算法。本项目提供了一个用C++实现的迷宫求解程序,让我们来深入探讨其中涉及的知识点。 1. **C++语言基础**:C++是一...

    数据结构(C语言版)课程设计(迷宫求解)

    在"数据结构(C语言版)课程设计(迷宫求解)"这个项目中,我们的目标是利用数据结构来解决迷宫问题。迷宫求解是一个典型的图遍历或搜索问题,它可以运用深度优先搜索(DFS)或广度优先搜索(BFS)等算法来解决。 ...

    c#迷宫求解算法

    在探讨C#迷宫求解算法时,我们深入解析一种基于深度优先搜索(Depth-First Search,简称DFS)的经典算法实现。此算法来源于严蔚敏的计算机算法理论,旨在通过递归或非递归的方式遍历迷宫的所有可能路径,找到从起点...

    迷宫求解 源代码 可执行程序

    《迷宫求解:TC2.0环境下的编程实践与解析》 对于计算机科学爱好者和初学者来说,解决迷宫问题是一项有趣的挑战,它能够帮助我们深入理解算法和数据结构的应用。本篇将围绕“迷宫求解源代码”进行详细讲解,特别...

    迷宫求解(8个方向),

    在IT领域,迷宫求解是一项经典的算法问题,它涉及到路径搜索、图论以及数据结构等多方面的知识。本文将详细解析"迷宫求解(8个方向)"这一主题,包括基本概念、算法原理和实现步骤。 迷宫通常被表示为一个二维网格,...

    数据结构与算法 迷宫求解

    本话题聚焦于"数据结构与算法 迷宫求解",这涉及到如何在二维空间中寻找一条从起点到终点的有效路径,尤其是在有障碍物(如墙壁)的情况下。迷宫求解算法通常用于游戏设计、路径规划等问题,它要求我们能够智能地...

    C++迷宫求解代码+报告

    在压缩包中的"迷宫求解.doc"很可能是详细的算法报告,包含了迷宫求解的理论分析、代码实现步骤以及可能的优化方法。"迷宫.exe"是编译后的可执行程序,使用者可以直接运行,查看迷宫求解的效果。最后一个文件名"迷宫...

    c语言数据结构迷宫求解

    c语言数据结构迷宫求解 严蔚敏版 使用栈和结构体

    数据结构之迷宫求解c++

    根据给定的信息,本文将对“数据结构之迷宫求解C++”这一主题进行深入解析,主要包括迷宫求解的背景、所涉及的关键数据结构、算法原理以及具体实现细节。 ### 迷宫求解背景 迷宫求解是计算机科学中的一个经典问题...

    栈的应用 - 迷宫求解

    本项目“栈的应用 - 迷宫求解”深入展示了如何利用栈来解决实际问题,特别是解决迷宫问题。迷宫问题是一个经典的路径搜索问题,它在游戏开发、算法设计以及计算机图形学等领域都有广泛应用。 栈在迷宫求解中的作用...

Global site tag (gtag.js) - Google Analytics