数据结构学习-迷宫问题

其他相关文章

使用栈数据结构进行全排序
数据结构 - 广度搜索 -迷宫问题
数据结构- 炸弹人游戏
数据结构 - 树 堆

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

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

一号代码主要来自书上

#include
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;//表示第stap个箱子遍历放入 1-9
         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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

二号代码来源于博客

#include 
#include 
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

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

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好像使用循环，比较节省内存，仅仅只是对单个变量使用了多个栈空间，应该比较节省内存。