迷宫求解

cofftech

浏览: 87423 次
性别:
来自: 成都

最近访客更多访客>>

whatl

liaoyang.777

cmddd

wqwqwq

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法

算法

采用了以栈为基础，在栈的基础上进行迷宫的求解，用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