数据结构(C语言):迷宫问题

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

【基本要求】

【测试数据】

【实现提示】
使用穷举法和栈求解

【代码过程】

1。

//base.h

//------------------- 公用的常量和类型 ----------------------------

#include<stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <string.h>

//函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status; //函数的返回值

typedef int DirectiveType; //下一个通道方向

#define RANGE 100 //迷宫大小

//~

2。

//stack.h

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

//------------ 栈的顺序存储实现 ------------------------------

typedef struct{

int row;

int col;

}PosType;

typedef struct{

int step; //当前位置在路径上的"序号"

PosType seat; //当前的坐标位置

DirectiveType di; //往下一个坐标位置的方向

}SElemType;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

//----------------- 栈的基本操作的算法实现 --------------------------------

Status InitStack(SqStack &s){

s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType));

if(!s.base) exit(OVERFLOW);

s.top=s.base;

s.stacksize=STACK_INIT_SIZE;

return OK;

}

Status GetTop(SqStack s, SElemType &e ){

if( s.top == s.base) return ERROR;

e = *(s.top-1);

return OK;

}

Status 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(OVERFLOW);

s.top = s.base + s.stacksize;

s.stacksize += STACKINCREMENT;

}

*s.top++ = e;

return OK;

}

Status Pop(SqStack &s, SElemType &e){

if(s.top==s.base)return ERROR;

e = * --s.top;

return OK;

}

int StackEmpty(SqStack s)

{

return s.base == s.top;

}

Status ClearStack(SqStack &s)

{

s.top = s.base;

return OK;

}

//~

3。

//maze.h

//-------------------- 迷宫程序 ----------------------------------

/**************************************************************

迷宫问题算法: 从入口出发,顺着某一个方向进行探索,若能走通,则继续

前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路,

假如所有可能的通路都探索到而未能达到出口,则所设定的迷宫没有通路.

说明:可通: 未增走到过的通道快.

*********************************************************/

#define ROW 9 //迷宫的行数

#define COL 8 //迷宫的列数

typedef struct{

int m,n;

int arr[RANGE][RANGE];

}MazeType; //迷宫类型

Status InitMaze(MazeType &maze, int a[][COL], int row, int col){

//按照用户输入的row行和col列的二维数组(0/1)

//设置迷宫maze的初值,包括加上边缘一圈的值

for(int i=1;i<=row;i++){

for(int j=1;j<=col;j++){

maze.arr[i][j] = a[i-1][j-1];

}

//加上围墙

for(int j=0;j<=col+1;j++){

maze.arr[0][j] = maze.arr[row+1][j]=1;

}

for(i=0;i<=row+1;i++){

maze.arr[i][0] = maze.arr[i][col+1]=1;

}

maze.m = row, maze.n = col;

return OK;

}

Status Pass(MazeType maze,PosType curpos){

//判断当前节点是否通过

return maze.arr[curpos.row][curpos.col] == 0;

}

Status FootPrint(MazeType &maze,PosType curpos){

//留下足迹

maze.arr[curpos.row][curpos.col]='*';

return OK;

}

Status MarkPrint(MazeType &maze,PosType curpos){

//留下不能通过的标记

maze.arr[curpos.row][curpos.col]='@';

return OK;

}

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){

//返回当前节点的下一节点

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;

}

Status PosEquare(PosType pos1, PosType pos2){

//判断两节点是否相等

return pos1.row==pos2.row && pos1.col==pos2.col ;

}

void PrintMaze(MazeType maze,int row,int col){

//打印迷宫信息

for(int i=1;i<=row;i++){

for(int j=1;j<=col;j++){

switch(maze.arr[i][j])

{

case 0:

printf(" ");

break;

case '*':

printf("* ");

break;

case '@':

printf("@ ");

break;

case 1:

printf("# ");

break;

}

printf(" ");

}

Status MazePath(MazeType &maze,PosType start, PosType end){

//求解迷宫maze中,从入口start到出口end的一条路径

//若存在,返回TRUE,否则返回FALSE

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( PosEquare(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);curstep--; //留下不能通过的标记,并退回一步

}

if(e.di<4){

e.di++; Push(s,e); //换一个方向探索

curpos = NextPos(e.seat,e.di); //求下一个节点

}

}while(!StackEmpty(s));

return FALSE;

}

//~

4。

//test.cpp

#include "base.h"

#include "stack.h"

#include "maze.h"

/**************** 测试 ***********************************/

void main()

{

int a[ROW][COL];

printf("enter the maze's data: ");

for(int i=0;i<ROW;i++)

{

for(int j=0; j<COL;j++)

{

scanf("%d",&a[i][j]);

}

PosType start,end;

start.row = 1;start.col=1;

end.row = 9; end.col = 8;

MazeType maze;

InitMaze(maze,a,ROW,COL);

Status ok = MazePath(maze,start,end);

if(ok) PrintMaze(maze,ROW,COL);

else printf("没有找到通路");

}

//~