迷宫寻址代码分析 谁借莪1个温暖的怀抱¢ 2022-07-15 02:54 93阅读 0赞 最近学了堆栈,里面有个迷宫寻址的程序蛮有意思的,觉得程序的思路也很厉害。 以下代码的迷宫寻址函数是《数据结构、算法与应用 C++语言描述》上的,自己也有一点小的改动。其中关于代码的分析都在注释中了,希望能看懂。 #include<iostream> using namespace std; struct Position { friend ostream& operator<<(ostream& out, Position& x); int row, col; }; ostream& operator<<(ostream& out, Position& x) { cout << x.row << "," << x.col; return out; } template<typename T> class Stack { public: Stack(int size); ~Stack() { delete[] stack; } int Size()const { return top + 1; } bool IsEmpty() { return top == -1; } bool IsFull() { return top == size - 1; } void Add(const T& x);//往stack栈顶添加元素 void Delete(T& x);//删除stack栈顶,并将删除的元素给x void Output()const;//输出stack中的所有元素 private: T* stack; int size; int top; }; template<typename T> Stack<T>::Stack(int size) { this->size = size; stack = new T[size]; top = -1; } template<typename T> void Stack<T>::Add(const T& x) { if (IsFull()) throw "THIS STACK IS FULL"; stack[++top] = x; } template<typename T> void Stack<T>::Delete(T& x) { if (IsEmpty()) throw "THIS STACK IS EMPTY"; x = stack[top--]; } template<typename T> void Stack<T>::Output()const { for (int i = 0; i <=top; i++) cout << stack[i]<<endl; } static Stack<Position>* path; //用来存放路径 //迷宫寻址函数 bool FindPath(int m,int n,int** maze) { //寻找从位置(1,1)到出口(n,n)的路径 //成功返回true,失败返回false path = new Stack<Position>(m*n-1); //对偏移量进行初始化 Position offset[4]; offset[0].row = 0; offset[0].col = 1;//往右走 offset[1].row = 1; offset[1].col = 0;//往下走 offset[2].row = 0; offset[2].col = -1;//往左走 offset[3].row = -1; offset[3].col = 0;//往上走 //在迷宫周围增加一圈障碍物:1表示能走,0表示不能走 for (int i = 0; i <= m + 1; i++)maze[0][i] = maze[m+1][i] = 0;//顶部和底部 for (int i = 0; i <= n + 1; i++)maze[i][0] = maze[i][n+1] = 0;//左部和右部 //输出迷宫 /* for (int i = 0; i <= m + 1; i++) { for (int j = 0; j <= n + 1; j++) cout << maze[i][j] << " "; cout << endl; } */ Position here; here.row = here.col = 1; maze[1][1] = 0;//设为0防止到时候回到起点 int option = 0;//选择走的方向:0往右走 1往下走 2往左走 3往上走 int maxOption=3;//能选择的最大option while (!(here.row == m && here.col == n))//还没走到终点的时候继续寻址 { //寻找并移动到一个相邻的位置 int row, col; while (option <= maxOption) { row = here.row + offset[option].row; col = here.col + offset[option].col; if (maze[row][col])break;//某个方向能走时退出循环尝试寻址 option++; } //找到能走的相邻位置 if (option <= maxOption) { //这里的策略是将here作为一个候选者,先不将here放到path中去,如果here周围有能走的Position,将那个Position作为新的here,而原先的here放到path中去 path->Add(here); here.row = row; here.col = col; //设置障碍继续寻址,防止新的here在寻址时将之前的here作为可走的路 maze[row][col] = 0; option = 0;//开始在新的here附近找能走的路 } //没有找到能走的相邻位置 else { if (path->IsEmpty())return false;//没有找到相邻的能走的路,同时也没有退路,就返回false Position prePosition;//找不到能走的路就说明path栈顶的那个Position也是不能走的,所以要将原先的那个Position弹出栈 path->Delete(prePosition); /* 下面两行代码是关键,需要好好分析一下: 因为是找path,所以path中任意两个相邻元素在迷宫maze中的位置一定也是相邻的,而path栈顶那个prePosition也一定和候选者here是相邻的 先判断之前那个Position是不是和找不到可走路的here在同一行, 如果在同一行, (1)prePosition.col-here.col==1,即here在prePosition左侧,说明之前已经尝试过prePosition的右侧、下侧和左侧(根据之前的0右1下2左3上原则),那么接下来尝试走上侧的路; (2)prePosition.col-here.col==-11,即here在prePosition右侧,说明之前只尝试过prePosition的右侧,那么接下来尝试走下侧的路; 如果不在同一行(那么一定在同一列),分析过程同上。 注意如果这时option变成4后,说明prePosition也是一个四周都走不通的Position,那么还得退回到prePosition的prePosition,这类似于递归又回退,但又不是递归。因此如果此时option变成4后下一次直接跳到else中进行重新寻址 */ if (prePosition.row == here.row)option = 2 + prePosition.col - here.col; else option = 3 + prePosition.row - here.row; //这时候选的变成prePosition here = prePosition; } } return true; } int main() { int m,n; int** maze; //输入迷宫行数列数 cin >> m >> n; //生成迷宫,加上周围的“围墙” maze = new int*[m + 2]; for (int i = 0; i < m+2; i++)maze[i] = new int[n + 2]; //输入迷宫 for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) cin >> maze[i][j]; if (FindPath(m, n, maze)) path->Output(); else cout << "Can not find the way " << endl; system("pause"); } 下面是我的测试迷宫![这里写图片描述][20161030231346325] [20161030231346325]: /images/20220715/2ec85d49c8ac460698a31de8a4708211.png
还没有评论,来说两句吧...