一个简单的迷宫算法

水深无声 2022-09-25 13:21 135阅读 0赞

# 迷宫问题的求解是一个典型的问题，那仫如何找到迷宫的出口？在遇到死胡同的时候如何返回？如何防止走重复的路程？这就是我们要解决的问题了. #

# 一.设置迷宫 #

要打印一个简单的迷宫，我们理所当然的想到了利用二维数组，在迷宫的实现中我定义了一个MazeMap.txt的文件用来存储迷宫，在初始化的时候只需要将该迷宫从mazeMap.txt中读出来就可以了.

0-路

1-墙

![Center][]

# 二.如何找到迷宫的通路 #

(1).如果当前路径已经走过则要留下标记；如果走到死胡同也要留下标记，但是要体现回溯，所以这两种情况的标记最好不同

(2).找迷宫路径的可通路可理解为使用试探法.

即在一个结点的上，下，左，右四个方向进行试探，如果某一个方向满足迷宫位置要求则将该位置压栈；如果走到死胡同此时该位置的四个方向都不可通(之前已经将走过的路标记为2),我们只需要将该位置出栈即可.

(3).判断是否走出迷宫.

因为迷宫的出口只可能在边界，我们可以认为三个方向都可能存在出口.所以在判断是否走出迷宫的时候,我们可以在除了入口的那一面都进行判断.

迷宫问题也是栈的应用场景之一

# 三.实现场景.(体现回溯和找到迷宫出口) #

在迷宫中用到的栈是我自己写的.

![Center 1][]

template<typename T>
    class Stack
    {
    public:
    	Stack()
    		:_ptr(NULL)
    		,_size(0)
    		,_capacity(0)
    	{}
    	~Stack()
    	{
    		if(_ptr != NULL)
    		{
    			delete[]_ptr;
    			_ptr=NULL;
    		}
    		_size=0;
    		_capacity=0;
    	}
    	void Push(const T& x)
    	{
    		_CheckCapacity();
    		_ptr[_size++]=x;
    	}
    	void Pop()
    	{
    		assert(_size >= 0);
    		_size--;
    	}
    	bool Empty()
    	{
    		return _size == 0;
    	}
    	T& Top()
    	{
    		return _ptr[_size-1];
    	}
    	size_t Size()
    	{
    		return _size;
    	}
    protected:
    	void _CheckCapacity()
    	{
    		if(_size == _capacity)
    		{
    			int NewCapacity=2*_capacity+2;
    			T *tmp=new T[NewCapacity];
    			//memcpy(tmp,_ptr,_size*sizeof(T));
    			for(int i=0;i<_size;i++)
    			{
    				tmp[i]=_ptr[i];
    			}
    			delete []_ptr;
    			_ptr=tmp;
    			_capacity=NewCapacity;
    		}
    	}
    protected:
    	T *_ptr;
    	int _size;
    	int _capacity;
    };

实现迷宫的基本算法.

const int N=10;
    
    struct Pos
    {
    	Pos(int row=0,int col=0)
    		:_row(row)
    		,_col(col)
    	{}
    	int _row;   //行
    	int _col;   //列
    };
    
    void InitMaze(int *mz)
    {
    	char tmp;
    	Pos enter;
    	FILE *pf=fopen("MazeMap.txt","r");
    	assert(pf);
    	for(size_t i=0;i<N;++i)
    	{
    		for(size_t j=0;j<N;)
    		{
    			tmp=fgetc(pf);
    			if(tmp == '0' || tmp == '1')
    			{
    				mz[i*N+j]=tmp-'0';
    				++j;
    			}
    		}
    	}
    }
    
    bool CheckReason(int *mz,Pos pos)
    {
    	if((pos._row >= 0) && (pos._col < N) && 
    		(pos._row >= 0) && (pos._col < N) && 
    		(mz[pos._row*N+pos._col] == 0))
    	{
    		return true;  //可通路
    	}
    	return false;     //不可通路
    }
    
    bool FindPath(int *mz,int rows,int cols,Stack<Pos>& s,Pos enter)
    {
    	s.Push(enter);
    	mz[enter._row*cols+enter._col]=2;
    	while(!s.Empty())     //如果栈为空说明该迷宫无解
    	{
    		Pos cur=s.Top();
    		Pos next=cur;
    		if((next._row == 0) || (next._row == rows-1) || (next._col == cols-1))
    			//判断是否走出迷宫
    		{
    			return true;
    		}
    		//上
    		next._row  -= 1;
    		if(CheckReason((int *)mz,next))
    		{
    			s.Push(next);
    			mz[next._row*cols+next._col]=2;   //经过的路置标记,防止走回头路
    			continue;
    		}
    		next._row += 1;
    		//右
    		next._col += 1;
    		if(CheckReason((int *)mz,next))
    		{
    			s.Push(next);
    			mz[next._row*cols+next._col]=2;
    			continue;
    		}
    		next._col -= 1;
    		//左
    		next._col -= 1;
    		if(CheckReason((int *)mz,next))
    		{
    			s.Push(next);
    			mz[next._row*cols+next._col]=2;
    			continue;
    		}
    		next._col += 1;
    		//下
    		next._row += 1;
    		if(CheckReason((int *)mz,next))
    		{
    			s.Push(next);
    			mz[next._row*cols+next._col]=2;
    			continue;
    		}
    		next._row  -= 1;
    
    		mz[cur._row*cols+cur._col]=3;   //体现回溯
    		s.Pop();
    	}
    	return false;
    }
    
    void PrintMaze(int *mz)
    {
    	for(size_t i=0;i<N;i++)
    	{
    		for(size_t j=0;j<N;j++)
    		{
    			cout<<mz[i*N+j]<<" ";
    		}
    		cout<<endl;
    	}
    	cout<<endl;
    }

在此迷宫问题中也可以找到走出此迷宫的最优路径，在这里用到图的广度优先可以解决...

[Center]: /images/20220717/faf471c29e91478abfada890d0ed0d28.png
[Center 1]: /images/20220717/3cde870f373f47cb9f4cdb37149c0b90.png