ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构(迷宫求解c++)

superlele123 分享于

2020腾讯云双十一活动,全年最低!!!(领取3500元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1073

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

推荐:数据结构之栈的应用----迷宫求解

/***********程序设计思想*************/ (1)迷宫地图相关: 利用动态二维数组来初步勾勒出迷宫: 建议先用malloc申请一维数组,再用calloc申请每个元素中的一

#include "sqstack.h"

Status InitStack(Stack &S)
{	
	S.top = 0 ; 
	for( int i = 0 ; i < MaxSize ; i++ ) 
	{ 
		S.data[i].di = 0 ; 
		S.data[i].ord = 0 ; 
		S.data[i].seat.c = 0; 
		S.data[i].seat.r = 0; 
	} 
return true; 	
}
Status DestroyStack(Stack &S)
{
	S.top = 0 ; 
	return true;
}
Status StackEmpty(Stack &S)
{
	if (S.top==0)
	return true; 
	else
	return false;
}
Status Push(Stack &S,SElemType &e)
{
	if(S.top<MaxSize){
		S.top++;
	S.data[S.top]=e;	
	return true;
	}
	else 
	return false;
	
}
Status Pop(Stack &S,SElemType &e)
{
	if(S.top>0){
		e=S.data[S.top];		
		S.top--;
	return true;
	}else 
	return false;
	
}




迷宫求解小游戏共三个头文件三个源文件,

下面先列出头文件再列出源文件:

#include <SDKDDKVer.h>
#pragma once
#define Status bool
#define TRUE true
#define FALSE false
struct PosType 
{
	int r,c;             //行列 or xy
};

typedef struct
{
	int ord;            //通道块在路径上的序号
	PosType seat;       //通道块在迷宫中的坐标位置
	int di;             //从此通道块走向下一通道块的方向
}SElemType;
extern bool drawflag;   //全局变量外部声明


 

#include <SDKDDKVer.h>
#pragma once
#define Status bool
#define TRUE true
#define FALSE false
struct PosType 
{
	int r,c;             //行列 or xy
};

typedef struct
{
	int ord;            //通道块在路径上的序号
	PosType seat;       //通道块在迷宫中的坐标位置
	int di;             //从此通道块走向下一通道块的方向
}SElemType;
extern bool drawflag;   //全局变量外部声明


 

推荐:数据结构:栈应用_求解迷宫问题3

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                          

#include <SDKDDKVer.h>
#include "selemtype.h"
#include "sqstack.h"
//#include "linkstack.h"
//迷宫大小
#define N 15
#define M 22
//分割块占总空间比例
#define V 0.4
typedef struct ElemType
{
	int x,y;
	char c;
}ElemType;
typedef struct MazeType
{
	ElemType arr[N][M];	
}MazeType;

Status Pass(MazeType &MyMaze, PosType CurPos);
void FootPrint(MazeType &MyMaze, PosType CurPos);
void MarkPrint(MazeType &MyMaze, PosType CurPos);
PosType NextPos(PosType CurPos, int Dir);

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

 

/*------------------------------------------------
    走迷宫算法v1.0
N            迷宫行数
M            迷宫列数
V            分割块占总空间比例
ElemType     迷宫元素类型
MazeType     迷宫类型

函数MazePath   走迷宫算法
函数Pass       判断当前位置是否可通过
函数FootPrint  留下足迹
函数MarkPrint  留下不能再走的标记
函数NextPos    计算下一位置
-------------------------------------------------*/
#include <iostream>
#include "MazePath.h"
Status MazePath(MazeType &maze, PosType start, PosType end)
{
	// 算法3.3
	// 若迷宫maze中从入口 start到出口 end的通道,则求得一条存放在栈中
	// (从栈底到栈顶),并返回TRUE;否则返回FALSE	    
	int curste=0;//记录所走的布数	
	Stack S;//定义一个栈
	InitStack(S);//实例化栈
	PosType curpos=start;//定义当前位置为开始位置
	SElemType e;
			
	do{	
		curste++;//探索下一步 
		if (Pass(maze,curpos)){//如果可以通过
			FootPrint(maze,curpos);//li留下已走过的印记
			e.di=1;
			e.ord=curste;
			e.seat=curpos;
			Push(S,e);//如果当前位置可以通过,入栈
			if (curpos.c==end.c&&curpos.r==end.r){//当前位置如果是终点
			return true;			
			}
			curpos=NextPos(curpos,1);//下一位置是但前位置的东临
			//curste++;//探索下一步 
		}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;
} // MazePath

Status Pass( MazeType &MyMaze,PosType CurPos) 
{
	if (MyMaze.arr[CurPos.r][CurPos.c].c==' ')
		return 1;     // 如果当前位置是可以通过,返回1
	else return 0;  // 其它情况返回0
}

void FootPrint(MazeType &MyMaze,PosType CurPos) 
{
	//循环是判断全局线程互斥变量的值,等待走步,
	//值为false,迷宫走步,并重新设为true,交给
	//主线程绘制,子线程等待
	while(drawflag)
		;
	drawflag=true;
	MyMaze.arr[CurPos.r][CurPos.c].c='*';
	
}

void MarkPrint(MazeType &MyMaze,PosType CurPos) 
{
	//循环是判断全局线程互斥变量的值,等待走步,
	//值为false,迷宫走步,并重新设为true,交给
	//主线程绘制,子线程等待
	while(drawflag)
		;
	drawflag=true;
	MyMaze.arr[CurPos.r][CurPos.c].c='!';
}

PosType NextPos(PosType CurPos, int Dir) 
{
	PosType ReturnPos; 
	switch (Dir) 
	{
    case 1:
        ReturnPos.r=CurPos.r;
        ReturnPos.c=CurPos.c+1;
        break;
    case 2:
        ReturnPos.r=CurPos.r+1;
        ReturnPos.c=CurPos.c;
        break;
    case 3:
        ReturnPos.r=CurPos.r;
        ReturnPos.c=CurPos.c-1;
        break;
    case 4:
        ReturnPos.r=CurPos.r-1;
        ReturnPos.c=CurPos.c;
        break;
	}
	return ReturnPos;
}


 

#include <iostream>
using namespace std;
#include "graphics.h"
#include <time.h>
#include "mazepath.h"
/*------------------------------------------------
    走迷宫游戏v1.0
屏幕大小:   640*480
Width        每个小方块宽度
Space        每个小方块间隔
Step         每块占据象素

drawflag     线程互斥全局变量,为true画图,
             为false走迷宫
threadflag   判断线程是否结束的全局变量,为false
             线程结束,程序结束
maze;        迷宫全局对象
start,mymyend    迷宫起终点全局变量


函数InitMaze        初始化迷宫
函数RandmMaze       随机生成迷宫
函数DrawMaze        绘制迷宫
函数ThreadMazePath  子线程函数,调用走迷宫函数修
                    改迷宫对象数据
    算法设计思想
数据结构:     迷宫每个元素由位置坐标x,y和是否可走
               的状态c构成,x、y代表画块的左上角坐
			   标,c为#是障碍,为空格是空位,为!
			   是已走过且不能再走,为*是走过且还有
			   选择;
基本操作:     栈的初始化、销毁、入栈、出栈等;
绘制迷宫操作: 在主线程中绘制,根据元素值c选择不同
               颜色绘制,根据元素值x、y,确定绘制
			   位置;
走迷宫操作:   在子线程中计算迷宫对象走动的每一步,
               修改迷宫对象的值,但不绘制迷宫,通
			   过修改互斥变量drawflag的值,在两个
			   线程中交替进行绘制和走步。				
-------------------------------------------------*/
#define Width 24
#define Space 2
#define Step  (Width + Space)

bool drawflag=true;
MazeType maze;
PosType mymyend;
PosType start;

bool threadflag=true;

void InitMaze(MazeType &maze)
{
	//初始化迷宫,将二维数组的每个元素计算出屏幕坐标
	int i,j;
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
		{
			maze.arr[i][j].x=30+j*Step;
			maze.arr[i][j].y=30+i*Step;
		}
}
void RandmMaze(MazeType &maze,PosType start,PosType mymyend)
{
	//随机生成迷宫,在二维数组内除起终点外其余位置随
	//机生成障碍,障碍数量按比例V计算
	int i,j,k,num;
	//边界和空位初始化
	for(i=0;i<N;i++)
	{
		maze.arr[i][0].c='#';
		maze.arr[i][M-1].c='#';		

		if(i!=0&&i!=N-1)
		{
			for(j=1;j<M-1;j++)
			{
				maze.arr[i][j].c=' ';
			}
		}
	}
	for(i=1;i<M-1;i++)
	{
		maze.arr[0][i].c='#';
		maze.arr[N-1][i].c='#';
	}

	//按分割块占总空间比例随机生成迷宫
	num=(N-2)*(M-2)*V;   //计算需要的分割块数量

	maze.arr[start.r][start.c].c='#'; //为了随机生成分割块不占用起始和终止位置
	maze.arr[mymyend.r][mymyend.c].c='#';

	k=num; 
	while(k>1)
	{
		i=rand()%(N-2)+1;j=rand()%(M-2)+1;
		if(maze.arr[i][j].c==' ')
			maze.arr[i][j].c='#';
		k--;
	}
	maze.arr[start.r][start.c].c=' ';
	maze.arr[mymyend.r][mymyend.c].c=' ';	

}
void DrawMaze(MazeType &maze)
{
	//绘制迷宫,按不同状态绘制不同颜色方块
	int i,j;
		
	for(i=0;i<N;i++)
	{
		for(j=0;j<M;j++)
		{
			switch(maze.arr[i][j].c)
			{
			case '#':   //障碍块
				setfillstyle(SOLID_FILL,LIGHTBLUE);
				break;
			case '!':   //已走过且无路可走的块
				setfillstyle(SOLID_FILL,LIGHTRED);
				break;
			case '*':   //走过的块
				setfillstyle(SOLID_FILL,LIGHTGREEN);
				break;
			case ' ':   //空闲块
				setfillstyle(SOLID_FILL,BLACK);
				break;
			}
			bar(maze.arr[i][j].x,maze.arr[i][j].y,maze.arr[i][j].x+Width,maze.arr[i][j].y+Width);
		}
		//cout<<mymyendl;
	}

}

DWORD WINAPI ThreadMazePath(LPVOID plParameter)
{
	//子线程函数,调用走迷宫函数修改迷宫对象数据
	//迷宫无解再生成新迷宫,直到有解
	int k=1;
	srand(time(0));
	RandmMaze(maze,start,mymyend); //随机生成迷宫

	while(!MazePath(maze,start,mymyend))
	{		
		cout<<"第"<<k<<"个迷宫无解!"<<endl;
		
		getchar();
		RandmMaze(maze,start,mymyend);k++;		
	}
	cout<<"第"<<k<<"个迷宫有解!"<<endl;
	
	setfillstyle(SOLID_FILL,BLACK);
	bar(100,450,500,480);
	setcolor(YELLOW);
	SetFont(16,16,0,0,0,FALSE,FALSE,FALSE,"宋体"); //文字设为宋体
	outtextxy(100,450,"此迷宫有通路!");

	threadflag=false;  //线程结束标记
	return 0;
}
void main()
{
	//初始化图形界面
	initgraph(640,480);
	//清屏
	cleardevice();

	//默认全局变量为true
	drawflag=true;   
	threadflag=true;

	
	InitMaze(maze);     //初始化迷宫对象
	
	start.r=start.c=1;  //初始化起终点
	mymyend.r=N-2;mymyend.c=M-2;

	//创建走迷宫数据计算子线程
	HANDLE hThread1=CreateThread(NULL,
        0,ThreadMazePath,NULL,0,NULL);
	

	while(threadflag)   //子线程未结束
	{
		Sleep(100);
		if(drawflag)     //线程互斥变量为真,画图,否则等待迷宫走完一步
		{
			DrawMaze(maze);	
			drawflag=false;  //画完一步,置为假,迷宫数据计算子线程走下一步
		}
	}

	
	//结束前任意键暂停
	getchar();
	//关闭图形界面
	closegraph();

}



 

 

推荐:C++数据结构与算法-----------

1、以数组为存储结构的二叉树     模板+完全二叉树(适合完全二叉树存储) /* 二叉树的线性存储  ..用数组  作为存储结构 ,需要对二叉树 按照层次进行编号  。适合

#include "sqstack.h"Status InitStack(Stack &S){ S.top = 0 ; for( int i = 0 ; i < MaxSize ; i++ ) { S.data[i].di = 0 ; S.data[i].ord = 0 ; S.data[i].seat.

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。