mazepath.cpp

迷宫问题是一个经典的问题

// mazepath.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stack.h"
#include "malloc.h"

#define RANGE 10	//设置数组的最大长度


typedef int DirectType;

typedef struct {
	int r,c;	//迷宫中r行c列的位置
}PosType;

typedef struct {
	int row,col;
	char arr[RANGE][RANGE];//各位置取值' ','#','@'或'*'
}MazeType;


typedef struct {
	int step;			//当前位置在路径上的“序号”
	PosType seat;		//当前的坐标位置
	DirectType di;		//往下一坐标位置的方向
}ElemType;				//栈的元素类型


typedef struct NodeType {
	ElemType data;		
	struct NodeType *next;
}NodeType,*LinkType;	//结点类型，指针类型

typedef struct {
	LinkType top;
	int size;
}Stack;					//栈类型
					

void Initialization(){
	printf("CreatMaze-c\n");
	printf("MazePsth-c\n");
	printf("PrintMaze-c\n");
}

void MakeNode(LinkType &p,ElemType e){
	p=(LinkType)malloc(sizeof(NodeType));
	p->data.step=e.step;
	p->data.seat.r=e.seat.r;
	p->data.seat.c=e.seat.c;
	p->data.di=e.di;
}

void FootPrint(MazeType &Maze,PosType curpos){
	Maze.arr[curpos.r][curpos.c]='*';
}

int Pass(MazeType &Maze,PosType curpos){
	if(Maze.arr[curpos.r][curpos.c]=='#'||Maze.arr[curpos.r][curpos.c]=='#')
		return 0;
	else return 1;
}
		


void CreateMaze(MazeType &Maze){
	int i,j;
	printf("产生迷宫：输入迷宫的大小\n");
	printf("行：\n");
	scanf("%d",&Maze.row);
	printf("列：\n");
	scanf("%d",&Maze.col);
	//给迷宫四周加障碍
	for(i=0;i<=Maze.row+1;i++)
		for(j=0;j<=Maze.col+1;j++)
			if(i==0||i==Maze.row+1)Maze.arr[i][j]='#';
			else if(j==0||j==Maze.col+1)Maze.arr[i][j]='#';
			else Maze.arr[i][j]=' ';
	//接收障碍位置
	printf("如果设置障碍结束，请输入“q”,否则输入障碍所在行\n");
	scanf("%d",&i);
	while(i!='q'){
		printf("输入障碍所在列\n");
		scanf("%d",&j);
		Maze.arr[i][j]='#';
		printf("如果设置障碍结束，请输入“q”,否则输入障碍所在行\n");
		scanf("%d",&i);
	}
}

void MakePrint(MazeType &Maze,PosType curpos){
	Maze.arr[curpos.r][curpos.c]='@';
}


void NextPos(PosType &curpos,DirectType di){
	switch(di){
	case 1:curpos.c++;break;
	case 2:curpos.r++;break;
	case 3:curpos.c--;break;
	case 4:curpos.r--;break;
	}
}



void PrintMaze(MazeType Maze){
	int i,j;
	for(i=1;i<=Maze.row;i++){
		for(j=1;j<=Maze.col;j++){
			printf("%c",Maze.arr[i][j]);
		}
		printf("\n");
	}



int MazePath(MazeType Maze,PosType start,PosType end){
	PosType curpos;
	ElemTpye e;
	int curstep=1,found=0;
	InitStack(S);
	curpos=start;
	do{
		if(Pass(Maze,curpos)){
			FootPrint(Maze,curpos);
			e.step=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);
			if(curpos==end)found=1;
			else {
				curpos=NextPos(curpos,1);
				curstep++:
			}//else
		}//if
		else 
			if (!StackEmpty(S)){
				Pop(S,e);
				while(e.di==4&&!StackEmpty(S)){
					MarkPrint(Maze,e.seat);
					Pop(S,e);
					curstep--;
				}//while
				if(e.di<4){
					e.di++;
					Push(S,e);
					curpos=NextPos(e.seat,e.di);
				}//if
			}//if
	}while(!StackEmpty(S)&&!found);
	return found;
}//Mazepath