栈---解决迷宫问题

  迷宫问题，是栈的一个经典应用。在今多年的面试题中特别常见。本博主呢，也就研究了一二。

  若有一迷宫，如何寻找通路？

  解题思路：

     迷宫，可将其看成一个二维数组。给定一个入口，需要判断此入口的上下左右是否越界，是否有通路点。若有通路点，将此点前一个通路点记录并将其置为非0（防止访问下一个通路点时再次判断）。继续寻找下一个通路,...以此类推。若查找不到通路点，则需要回溯。判断是否还有其他通路。

回溯呢，就是将从记录的通路点回退。此特征呢，和我们的栈很相似。所以，栈就在此处派上用场喽。

    那么如何判断迷宫是否有通路呢？

    判断条件：（1）有通路。当行或者列到达边界时即可判断。

              （2）无通路。当回溯时，需要从栈中取出元素。当栈为空时即可判断。

  假设有如下迷宫。（迷宫中0为通路）入口点（2,0）。

分析：

    看到此迷宫，可将其看成二维数组。但是在程序中不可能一个一个输入（若迷宫很大呢）。所以可将其以文件的形式读取。我们看到在此迷宫处，有一个通路点处有两条通路，若先走下面，行到达边界处，则可直接得出有通路。若先右方，最终无通路可走，则需要回溯，在进一步的判断。当回溯到岔路口时，发现下方还有路可走。继续向下走，最终行到达边界处，即有通路。

程序实现：

"Maze.h"

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <assert.h> #include <stack> #define N 10 using namespace std; struct Pos {	int _row;//行	int _col;//列 }; //从文件中读出数据，并以一位数组存放 void GetMaze(int *a,int n)  {	FILE* f = fopen("test.txt","r");	assert(f);	for(int i=0;i<n;i++)	{	for(int j=0;j<n;)	{	char ch = fgetc(f);	if(ch == '0' || ch == '1')	{	a[i*n+j] = ch - '0';	j++;	}	else	{	continue;	}	}	} } //打印迷宫 void PrintMaze(int *a,int n) {	for(int i=0;i<n;i++)	{	for(int j=0;j<n;j++)	{	cout<<a[i*n+j]<<" ";	}	cout<<endl;	} } //是否有通路 bool PathIsAccess(int *a,int n,Pos next) {	assert(a);	if((next._row>=0)&&(next._row<n)&&(next._col>=0)&&	(next._col<n)&&(a[next._row*n+next._col] == 0))	{	return true;	}	return false; } bool  MazePath(int *a,int n,Pos& entry,stack<Pos>& path) {	 Pos cur = entry;	 path.push(cur);	 while(!path.empty())	 { 	 a[cur._row*n+cur._col] = 2;//压栈后将其置为2，防止再次访问到	 if((cur._col == n-1)||(cur._row == n-1))//通路条件，行或列到达边界	 {	 return true;	 }	 //上	 Pos next = cur; //将上一个通路点保存	 next._row--;	 if(PathIsAccess(a,n,next))//是否越界	 {	 cur = next;	 path.push(cur);	 continue;	 } 	  //左	 next = cur;	 next._col--;	 if(PathIsAccess(a,n,next))	 {	 cur = next;	 path.push(cur);	 continue;	 } 	 //右	 next = cur;	 next._col++;	 if(PathIsAccess(a,n,next))	 {	 cur = next;	 path.push(cur);	 continue;	 }	 //下	 next = cur;	 next._row++;	 if(PathIsAccess(a,n,next))	 {	 cur = next;	 path.push(cur);	 continue;	 }	 cur = path.top();//回溯	 path.pop();	 }	return false; } void Test() {	int a[N][N] = {};	GetMaze((int *)a,N);	PrintMaze((int *)a,N);	stack<Pos> path;	Pos entry = {2,0};	bool ret = MazePath((int *)a,N,entry,path);	cout<<"是否有通路"<<ret<<endl;	PrintMaze((int *)a,N); }

测试结果：

（1）先走右方（出现回溯）

（2）先走下方