[数据结构与算法]数据结构学习-迷宫问题

今天看了两个使用深度优先搜索算法求解迷宫问题的代码。两个有点不同，主要体现在

1. 2号代码没有对方向进行循环
2. 2号代码没有还原变量

一号代码主要来自书上

#include<iostream>
using namespace std;
#define N 5
#define M 4
int a[10],book[10],n;
void dfs(int step){
   if (step == 10){
         if (a[1]*100+a[2]*10+a[3] + a[4]*100+a[5]*10+a[6] == a[7]*100+ a[8]*10+a[9]) {
            cout << a[1]<<a[2]<<a[3] << "+" <<   a[4]<<a[5]<<a[6] << "=" <<  a[7]<<a[8]<<a[9] <<endl;

         }
   }

   for (int i=1;i<10;i++){
      if (book[i]==0){
         a[step] = i;
         book[i] = i;

         dfs(step+1);
         book[i] = 0;
      }
   }
}
template<int n, int m>
void show(int(&ary)[n][m])//利用引用形参接受含有特定数量元素的二维数组
{//让编译器帮我们推导n和m的值
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j) {
			cout << " " << ary[i][j] << " ";
		}
		cout << " " << endl;
	}
}
int x_t = 3,y_t = 2;
int x = 1,y=1;
int field[5][4] = {
   {0,0,1,0},
   {0,0,0,0},
   {0,0,1,0},
   {0,1,0,0},
   {0,0,0,1},
}; 
int pass_[5][4] = {0};
int direction_[4][2] ={
   {0,1},
   {1,0},
   {0,-1},
   {-1,0}
};
 int min_ = 100;
void dfs_2(int x, int y,int step){

   // 如果当前的坐标等于目标坐标，则return
   int tx=0,ty=0,k;
   if (x==x_t && y==y_t){
      show(pass_);
      std::cout<<endl;
      if (step<min_) min_ = step;
      return;
   };

   //基于当前深度的遍历:对于特定的方向， 对于某个节点进行循环遍历
   for (auto row:direction_){ 

      //执行下一步
      tx = x + *(row);
      ty  =  y+ *(row + 1); 
      //判断是否越界
      if (tx<0 || tx>4||ty<0||ty>3)
         continue;

         //判断是否为障碍物或在路上
         if (field[tx][ty]==0 && pass_[tx][ty]==0 )
{
         pass_[tx][ty] = 1; 

         dfs_2(tx,ty,step+1);
         pass_[tx][ty] = 0;  //退出记得还原操作
}
   }
}

int main(){
   pass_[0][0] = 1;
  
   //dfs(1);
   // 建立迷宫
   dfs_2(0,0,0);
}

二号代码来源于博客

#include <iostream>
#include <stack>
using namespace std;

struct Point{  
    //行与列
    int row;  
    int col;  
	Point(int x,int y){
		this->row=x;
		this->col=y;
	}

	bool operator!=(const Point& rhs){
		if(this->row!=rhs.row||this->col!=rhs.col)
			return true;
		return false;
	}
};  

//func:获取相邻未被访问的节点
//para:mark:结点标记，point：结点，m：行，n：列
//ret:邻接未被访问的结点
Point getAdjacentNotVisitedNode(bool** mark,Point point,int m,int n){
	Point resP(-1,-1);
	if(point.row-1>=0&&mark[point.row-1][point.col]==false){//上节点满足条件
		resP.row=point.row-1;
		resP.col=point.col;
		return resP;
	}
	if(point.col+1<n&&mark[point.row][point.col+1]==false){//右节点满足条件
		resP.row=point.row;
		resP.col=point.col+1;
		return resP;
	}
	if(point.row+1<m&&mark[point.row+1][point.col]==false){//下节点满足条件
		resP.row=point.row+1;
		resP.col=point.col;
		return resP;
	}
	if(point.col-1>=0&&mark[point.row][point.col-1]==false){//左节点满足条件
		resP.row=point.row;
		resP.col=point.col-1;
		return resP;
	}
	return resP;
}

//func：给定二维迷宫，求可行路径
//para:maze：迷宫；m：行；n：列；startP：开始结点 endP：结束结点； pointStack：栈，存放路径结点
//ret:无
void mazePath(void* maze,int m,int n,const Point& startP,Point endP,stack<Point>& pointStack){
	//将给定的任意列数的二维数组还原为指针数组，以支持下标操作
	int** maze2d=new int*[m];
	for(int i=0;i<m;++i)
	{
		maze2d[i]=(int*)maze + i*n;
	}

	//起点和终点必须为无障碍结点，否则输入错误
	if(maze2d[startP.row][startP.col] == 1 || maze2d[endP.row][endP.col] == 1)
	{
		return ;
	}

	//建立各个节点访问标记
	bool** mark=new bool*[m];
	for(int i=0;i<m;++i) {
		mark[i]=new bool[n];
	}
	for(int i=0;i<m;++i) {
		for(int j=0;j<n;++j)
		{
			mark[i][j]=*((int*)maze+i*n+j);
		}
	}

	//将起点入栈
	pointStack.push(startP);
	mark[startP.row][startP.col]=true;
	
	//栈不空并且栈顶元素不为结束节点
	while(pointStack.empty()==false&&pointStack.top()!=endP){
		Point adjacentNotVisitedNode=getAdjacentNotVisitedNode(mark,pointStack.top(),m,n);
		if(adjacentNotVisitedNode.row==-1){ //没有未被访问的相邻节点
			pointStack.pop(); //回溯到上一个节点
			continue;
		}

		//入栈并设置访问标志为true
		mark[adjacentNotVisitedNode.row][adjacentNotVisitedNode.col]=true;
		pointStack.push(adjacentNotVisitedNode);
	}
}

int main() {
	int maze[5][5]={
		{0,0,0,0,0},
		{0,1,0,1,0},
		{0,1,1,0,0},
		{0,1,1,0,1},
		{0,0,0,0,0}
	};

	Point startP(0,0);
	Point endP(4,4);
	stack<Point>  pointStack;
	mazePath(maze,5,5,startP,endP,pointStack);

	//没有找打可行解
	if(pointStack.empty()==true) {
		cout<<"no right path"<<endl;
	} else {
		stack<Point> tmpStack;
		cout<<"path:";
		while(pointStack.empty()==false) {
			tmpStack.push(pointStack.top());
			pointStack.pop();
		}
		while (tmpStack.empty()==false) {
			printf("(%d,%d) ",tmpStack.top().row,tmpStack.top().col);
			tmpStack.pop();
		}
	}
}

两个代码应该都可的。但是我先学习了一，看书上说：

1. 对于某个节点进行循环遍历，在单次遍历的时候进行嵌套调用 (可以看代码一对应的注释处)
2. 退出记得还原操作‘

但是我发现代码2：

1. 2号代码没有对方向进行循环
2. 2号代码没有还原变量

经过比较和学习，得出结论：

代码1还原变量的原因是：路径不能走入一个死胡同
代码2没有对方向进行循环的原因是：只要走过的格子（无论是不是死胡同）都进行了赋值
代码2 表面上没有使用嵌套，但是好像比嵌套更有效一点。

具体分析

1、 2号代码没有还原变量

代码1使用 pass_ 变量来存储目前路径，必须还原变量，防止走进死胡同，然而代码2由于使用了栈结构，栈里面的变量不可能重复。

2、 2号代码没有对方向进行循环

代码2 表面上没有对单个点进行多方向循环，实际上他利用自己未经过还原的 pass_变量（代码2中叫mark）把已走过的所有路（包括死胡同）都记录了，防止自己在同一个节点处一直往一个方向走。

3、 代码2 表面上没有使用嵌套，但是好像比嵌套更有效一点。

1号使用嵌套，嵌套实际上会申请多个栈空间，可能比较占用内存。代码2好像使用循环，比较节省内存，仅仅只是对单个变量使用了多个栈空间，应该比较节省内存。