赞
踩
使用栈数据结构进行全排序
数据结构 - 广度搜索 -迷宫问题
数据结构- 炸弹人游戏
数据结构 - 树 堆
今天看了两个使用深度优先搜索算法求解迷宫问题的代码。两个有点不同,主要体现在
- 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;//表示第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); }
二号代码来源于博客
#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(); } } }
两个代码应该都可的。但是我先学习了一,看书上说:
但是我发现代码2:
- 2号代码没有对方向进行循环
- 2号代码没有还原变量
经过比较和学习,得出结论:
代码1还原变量的原因是:路径不能走入一个死胡同
代码2没有对方向进行循环的原因是:只要走过的格子(无论是不是死胡同)都进行了赋值
代码2 表面上没有使用嵌套,但是好像比嵌套更有效一点。
代码1使用 pass_ 变量来存储目前路径,必须还原变量,防止走进死胡同,然而代码2由于使用了栈结构,栈里面的变量不可能重复。
代码2 表面上没有对单个点进行多方向循环,实际上他利用自己未经过还原的 pass_变量(代码2中叫mark)把已走过的所有路(包括死胡同)都记录了,防止自己在同一个节点处一直往一个方向走。
1号使用嵌套,嵌套实际上会申请多个栈空间,可能比较占用内存。代码2好像使用循环,比较节省内存,仅仅只是对单个变量使用了多个栈空间,应该比较节省内存。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。