main.cpp

用C++编写的迷宫求路径算法

#include<iostream>
using namespace std;
#include<time.h>

#define N 9 //迷宫规模

struct point
{
	int x;
	int y;
};
point foot[20]; 

//初始化迷宫 起始点a[0][0] 出口a[N-1][N-1]
//为0表示可以通过，为1表示不能通过
void init(int a[][N])
{
	int i, j;
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			a[i][j] = 1;
	//至少一条通路
	for(i = 0; i < N; i++)
	{
		a[0][i] = 0;
		a[i][N-1] = 0;
	}
	
	srand(time(NULL));
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			if(a[i][j])
				a[i][j] = rand() % 2;

	//输出迷宫
	cout<<"   ";
	for(i = 0; i < N; i++)
		cout<<" "<<i;
	cout<<endl<<"   ";
	for(i = 0; i < N; i++)
		cout<<" "<<'*';
	cout<<endl;
	for(i = 0; i < N; i++)
	{
		cout<<i<<" * ";
		for(j = 0; j < N; j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}			
}

//寻找路径
void look(int a[][N])
{
	point *pt = foot - 1; //路径栈
	//起始点
	int i, j;
	i = j = 0; 
	//起始点入栈
	++pt;
	pt->x = i;
	pt->y = j;
	a[i][j] = 2; //该点被寻找过

	while((i != N -1 ) || (j != N - 1))
	{
		i = pt->x;
		j = pt->y;
		if(i + 1 < N && a[i+1][j] == 0) //下
		{
			++pt;
			pt->x = ++i;
			pt->y = j;
			a[i][j] = 2;
		}
		else if(j + 1 < N && a[i][j+1] == 0) //右
		{
			++pt;
			pt->x = i;
			pt->y = ++j;
			a[i][j] = 2;
		}
		else if(i - 1 >= 0 && a[i-1][j] == 0) //上
		{
			++pt;
			pt->x = --i;
			pt->y = j;
			a[i][j] = 2;
		}
		else if(j - 1 >= 0 && a[i][j-1] == 0) //左
		{
			++pt;
			pt->x = i;
			pt->y = --j;
			a[i][j] = 2;
		}
		else //当前无路径，回退
			pt--;
	}//while

	//输出路径
	for(point *p = foot; p <= pt; p++)
		cout<<"("<<p->x<<" , "<<p->y<<")\t";
	cout<<endl;
}

void main()
{
	cout<<"0表示通路，1表示障碍"<<endl<<endl;
	int a[N][N];
	init(a);
	look(a);	
}