graph.cpp

实现走迷宫的功能

#include"stdafx.h"
#include<iostream>
#include<Stack>
#include<Time.h>

using namespace std;

#define ROW 16
#define COL 16
//迷宫随机生成  利用图的深度优先遍历
class Graph{
private:
int maze[2*ROW+3][2*COL+3];  //迷宫矩阵 包括路径和顶点
int design[ROW+1][COL+1];    //追踪顶点 标记是否遍历
int current;               
int a[10000][2];             //存放顶点的行数和列数
stack<int*> graph;
int num;
public:

//获取随机数
int get_rand()
{
	int p = rand();
	return p;
}

//深度优先遍历  将邻接点存放入暂时创建的战中以回溯
void DFS(int cur1,int cur2)
{
	design[cur1][cur2]=++num;
	a[current][0]=cur1;
	a[current][1]=cur2;
	graph.push(a[current]);
	current++;
	stack<int*> graph2;
	int current1=0;
	int b[4][2];
	
	int sort1=get_rand()%4;
	int sort2=get_rand()%3;
	int sort3=get_rand()%2; 
	switch(sort1)                              //随机访问邻接点
	{
	case 0:
		if(cur1<ROW&&design[cur1+1][cur2]==0)
		{
			
				b[current1][0]=cur1+1;b[current1][1]=cur2;
				graph2.push(b[current1]);current1++;
				
			}
			switch(sort2)
			{
			case 0:
				if(cur1>=1&&design[cur1-1][cur2]==0)
				{
					
					b[current1][0]=cur1-1;b[current1][1]=cur2;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
					
					}
					break;
				}
				break;
			case 1:
				if(cur2<COL&&design[cur1][cur2+1]==0)
				{
					
					b[current1][0]=cur1;b[current1][1]=cur2+1;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				}
				break;
			case 2:
				if(cur2>=1&&design[cur1][cur2-1]==0)
				{
					
					b[current1][0]=cur1;b[current1][1]=cur2-1;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2<COL-1&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				}
				break;
			}
			break;
		case 1:
			if(cur1>=1&&design[cur1-1][cur2]==0)
			{
				
				b[current1][0]=cur1-1;b[current1][1]=cur2;
				graph2.push(b[current1]);current1++;
				
			}
			switch(sort2)
			{
			case 0:
				if(cur2<COL&&design[cur1][cur2+1]==0)
				{
					
					b[current1][0]=cur1;b[current1][1]=cur2+1;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				}
				break;
			case 1:
				if(cur2>=1&&design[cur1][cur2-1]==0)
				{
					
					b[current1][0]=cur1;b[current1][1]=cur2-1;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				}
				break;
			case 2:
				if(cur1<ROW&&design[cur1+1][cur2]==0)
				{
					
					b[current1][0]=cur1+1;b[current1][1]=cur2;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				}
				break;
			}
			break;
		case 2:
			if(cur2<COL&&design[cur1][cur2+1]==0)
			{			
				
				b[current1][0]=cur1;b[current1][1]=cur2+1;
				graph2.push(b[current1]);current1++;
				
			}
			switch(sort2)
			{
			case 0:
				if(cur1<ROW&&design[cur1+1][cur2]==0)
				{
					
					b[current1][0]=cur1+1;b[current1][1]=cur2;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}						
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}		
					break;
				}
				break;
			case 1:
				if(cur2>=1&&design[cur1][cur2-1]==0)
				{
					
					b[current1][0]=cur1;b[current1][1]=cur2-1;
					graph2.push(b[current1]);current1++;
					
				}
				switch(sort3)
				{
				case 0:
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}		
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}	
					break;
				}
				break;
			case 2:
				if(cur1>=1&&design[cur1-1][cur2]==0)
				{
					
					b[current1][0]=cur1-1;b[current1][1]=cur2;
					graph2.push(b[current1]);current1++;
					
				}		
				switch(sort3)
				{
				case 0:
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				case 1:
					if(cur2>=1&&design[cur1][cur2-1]==0)
					{
						b[current1][0]=cur1;b[current1][1]=cur2-1;
						graph2.push(b[current1]);current1++;
						
					}
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
						
					}
					break;
				}
				break;
			}
			break;
		case 3:
			if(cur2>=1&&design[cur1][cur2-1]==0)
			{
				
				b[current1][0]=cur1;b[current1][1]=cur2-1;
				graph2.push(b[current1]);current1++;
				
			}
			switch(sort2)
			{
			case 0:
				if(cur1<ROW&&design[cur1+1][cur2]==0)
				{
					
					b[current1][0]=cur1+1;b[current1][1]=cur2;
					graph2.push(b[current1]);current1++;
				}
				switch(sort3)
				{
				case 0:
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}		
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;

					}
					break;
				case 1:
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
					}
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					break;
				}
				break;
			case 1:
				if(cur2<COL&&design[cur1][cur2+1]==0)
				{
					
					b[current1][0]=cur1;b[current1][1]=cur2+1;
					graph2.push(b[current1]);current1++;
				}
				switch(sort3)
				{
				case 0:
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					break;
				case 1:			
					if(cur1>=1&&design[cur1-1][cur2]==0)
					{
						
						b[current1][0]=cur1-1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					break;
				}
				break;
			case 2:
				if(cur1>=1&&design[cur1-1][cur2]==0)
				{
					
					b[current1][0]=cur1-1;b[current1][1]=cur2;
					graph2.push(b[current1]);current1++;
				}
				switch(sort3)
				{
				case 0:
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
					}
					break;
				case 1:
					if(cur2<COL&&design[cur1][cur2+1]==0)
					{
						b[current1][0]=cur1;b[current1][1]=cur2+1;
						graph2.push(b[current1]);current1++;
					}
					if(cur1<ROW&&design[cur1+1][cur2]==0)
					{
						
						b[current1][0]=cur1+1;b[current1][1]=cur2;
						graph2.push(b[current1]);current1++;
					}
					break;
				}
				break;
			}
			break;
		}
		while(!graph2.empty())
		{
			int* p = graph2.top();
			cur1=p[0];
			cur2=p[1];
			graph2.pop();
			if(design[cur1][cur2]==0)
			{
				DFS(cur1,cur2);
			}
		}   
}

void DepthGraph()
{

	current=0;
	num = 0;
	int cur1=0,cur2=0;
	// 0表示墙  1表示通道 2表示入口 3表示出口
	for(int i = 0;i<=2*ROW+2;i++)
	{
		for(int j = 0;j <= 2*COL+2;j++)
		{
			maze[i][j]=0;
		}
	}
	int i = 0,j = 0;
	srand(time(0));  //获取生成随机数的种子

	//递归进行图的深度遍历
	while(num<(ROW+1)*(COL+1))
	{
		while(design[i][j]!=0)
		{
			if(j<COL)
				j++;
			else if(i<=ROW)
			{
				i++;
				j = 0;
			}
		}
		cur1=i;
		cur2=j;
		DFS(cur1,cur2);
	}

	//根据深度遍历的结果建立迷宫数组
	while(!graph.empty())
	{
		int *p1=graph.top();
		int pcur1=p1[0];int pcur2=p1[1];
		design[pcur1][pcur2]=0;
		graph.pop();
		maze[2*pcur1+1][2*pcur2+1]=1;
		if(!graph.empty())
		{
			int* p2=graph.top();
			cur1=p2[0];cur2=p2[1];
			if(!((cur1*(COL+1)+cur2)-(pcur1*(COL+1)+pcur2)==1||(pcur1*(COL+1)+pcur2)-(cur1*(COL+1)+cur2)==1||(pcur1*(COL+1)+pcur2)-(cur1*(COL+1)+cur2)==COL+1
		||(cur1*(COL+1)+cur2)-(pcur1*(COL+1)+pcur2)==COL+1))
			{
				if(pcur1>0&&design[pcur1-1][pcur2]!=0)
				{
					cur1=2*pcur1-1+1;
					cur2=2*pcur2+1;
				}
				else if(pcur1<ROW&&design[pcur1+1][pcur2]!=0)
				{
					cur1=2*pcur1+1+1;
					cur2=2*pcur2+1;
				}
				else if(pcur2>0&&design[pcur1][pcur2-1]!=0)
				{
					cur1=2*pcur1+1;
					cur2=2*pcur2-1+1;
				}
				else if(pcur2<ROW&&design[pcur1][pcur2+1]!=0)
				{
					cur1=2*pcur1+1;
					cur2=2*pcur2+1+1;
				}
			}
			else
			{
			if(pcur1==cur1+1)cur1=2*cur1+1+1;
			else if(pcur1==cur1-1)cur1=2*pcur1+1+1;
			else if(pcur1==cur1)cur1=2*cur1+1;
			if(pcur2==cur2+1) cur2=2*cur2+1+1;
			else if(pcur2==cur2-1)cur2=2*pcur2+1+1;
			else if(pcur2==cur2) cur2=2*cur2+1;
			}
			maze[cur1][cur2]=1;
		}
		maze[1][5]=2;    //设置入口
		maze[2*(ROW-1)-1][2*(COL-1)-1]=3;   //设置出口
	}
}

//获取迷宫数组
int* get_Maze(int i)
{
	if (i==0) DepthGraph();
	return maze[i];
}
};