maze.h

用矩阵表示的迷宫

#pragma once

#include "LinkedQueue.h"
//#include "Queue.h"
#include <iostream.h>
#define INVALID_DATA 10
//////////////////////////////////////////////////////////////////////
//enum DIR{L,R,U,D};
//////////////////////////////////////////////////////////////////////
class Position
{
public:
	Position(int x = 0,int y = 0){this->x = x;this->y = y;}
public:
	int x;
	int y;
public:
	bool operator ==(const Position&p)
	{
		if(p.x == x&&p.y == y)return true;
		return false;
	}
	Position&Offset(int d)
	{
		switch(d)
		{
		case 2:x--;break;
		case 0:x++;break;
		case 3:y--;break;
		case 1:y++;break;
		case 4:x++;y++;break;
		case 5:x--;y++;break;
		case 6:y--;x--;break;
		case 7:x++;y--;break;
		default:throw INVALID_DATA;
		}
		return *this;
	}
};
//////////////////////////////////////////////////////////////////////
class Maze
{
	friend ostream&operator<<(ostream&,Maze&);
public:
	Maze(int**m,int x,bool IsFourDir = true);
	~Maze();
public:
	bool FindWay(Position*&,int&);
	static bool FindWay(int**,int,Position*&,int&);
	void OutPutPath(ostream&);
private:
	const int n;
	int**mz;
	bool IsFourDir;
};
/////////////////////////////////////////////////////////////////////
Maze::Maze(int**m,int x,bool b):n(x+2),IsFourDir(b)
{
	if(x<10||x>50){mz = NULL;throw INVALID_SIZE;}
	mz = new int*[x+2];
	if(mz == NULL)throw NO_MEMORY;
	for(int i = 0;i<x+2;i++)
	{
		mz[i] = new int[x+2];
		if(mz[i] == NULL)throw NO_MEMORY;
	}
	for(int i = 0;i<x;i++)
		for(int j = 0;j<x;j++)
			if(m[i][j]!=0&&m[i][j]!=1)throw INVALID_DATA;
			else	mz[i+1][j+1] = m[i][j];
	for(int i = 0;i<x+2;i++)
		mz[0][i] = mz[i][0] = mz[x+1][i] = mz[i][x+1] = 1;
}
Maze::~Maze()
{
	if(mz==NULL)return;
	for(int i = 0;i<n;i++)
		if(mz[i]!=NULL)
		delete[]mz[i];
	delete[]mz;
}
/////////////////////////////////////////////////////////////////////
bool Maze::FindWay(Position*&way,int&size)
{
	int dir = 8;
	if(IsFourDir)dir = 4;
	Position here(1,1);
	const Position end(n-2,n-2);
	Position p;
	mz[1][1] = 2;
	//Queue<Position>Q(100);
	LinkedQueue<Position>Q;
	Q.Add(here);
	while(true)
	{		
		try{
			Q.Delete(here);}catch(int){return false;}
		for(int i = 0;i<dir;i++)
		{
			p = here;
			p.Offset(i);
			if(mz[p.x][p.y] == 0)//是还未经过的路
			{
				mz[p.x][p.y] = mz[here.x][here.y]+1;
				if(p == end)goto found;
				Q.Add(p);
			}
		}
	}
found:
	int data = mz[end.x][end.y];
	here = end;
	size = data-1;
	way = new Position[size];
	way[size-1] = end;
	for(int i = data-1;i>1;i--)
		for(int j = 0;j<dir;j++)
		{
			p = here;
			p.Offset(j);
			if(mz[p.x][p.y] == i)
			{
				way[i-2] = p;
				here = p;
				break;
			}
		}
	return true;
}
bool Maze::FindWay(int**m,int x,Position*& way,int&size)
{
	Maze mz(m,x);
	return mz.FindWay(way,size);
}
void Maze::OutPutPath(ostream&out)
{
	Position*ps;int size;
	if(!this->FindWay(ps,size)){out<<"no path!"<<endl;return;}
	out<<size<<endl;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			if(mz[i][j]==1)
			{out<<"█";continue;}
			bool b = false;
			for(int k = 0;k<size;k++)
				if(ps[k].x == i&&ps[k].y == j)b = true;
			if(b)out<<"¤";
			else out<<"  ";
		}
		out<<endl;
	}
}
////////////////////////////////////////////////////////////////////
ostream&operator<<(ostream&out,Maze&m)
{
	for(int i = 0;i<m.n;i++)
	{
		for(int j = 0;j<m.n;j++)
			if(m.mz[i][j]==1)
			out<<"█";
			else out<<"  ";
			
		out<<endl;
	}
	return out;
}