【数据结构】使用栈Stack解决迷宫问题-创新互联
我们看下面这个迷宫----方阵(也可以是矩阵):
10年积累的网站制作、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站设计后付款的网站建设流程,更有西华免费网站建设让你可以放心的选择与我们合作。迷宫入口是坐标(2,0)位置,出口是(9,3)。我们假定0代表通路,1代表不通。
现在需要找到哪一条路是通路。我们的思想是借助栈,“回溯法”。回溯是什么意思呢???先从起点出发,检查它的上下左右是否是通路(即是否有为数字0处)。也就是说为0通了,压栈,将此位置元素变成2,这样做的好处是明确通路路径。然后继续往下走,判断上下左右 。直至我们找到终点(纵坐标在矩阵的最后一行)。
我们来看下我针对迷宫问题实现的代码:
#include#include #define N 10 //该迷宫10*10. struct Pos //定义一个结构体,该结构体用来表示坐标。 { int _row; int _col; Pos(int row,int col) :_row(row) , _col(col) {} }; template bool SearchMazePath(int* a, int n, Pos entry, stack & paths) //寻找迷宫是否有通路。 { assert(a); paths.push(entry); while (!paths.empty()) { Pos cur = paths.top(); a[cur._row*n + cur._col] = 2; if (cur._row == n - 1) { return true; } //上 Pos tmp = cur; --tmp._row; if (a[tmp._row*n + tmp._col] == 0) { paths.push(tmp); continue; } //下 tmp = cur; ++tmp._row; if (a[tmp._row*n + tmp._col] == 0) { paths.push(tmp); continue; } //左 tmp = cur; --tmp._col; if (a[tmp._row*n + tmp._col] == 0) { paths.push(tmp); continue; } //右 tmp = cur; ++tmp._col; if (a[tmp._row*n + tmp._col] == 0) { paths.push(tmp); continue; } paths.pop(); //若上下左右都不通,则回溯。 } return false; } void GetMaze(int* a, int n) //读取到迷宫图案 { assert(a); FILE* fout = fopen("MazeMap.txt", "r"); assert(fout); //若文件打开失败,后续工作则无法完成,因此采用assert防御式编程。 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { while (true) { int men = fgetc(fout); //读取字符 if (men == '0' || men == '1') //是0或者1则转换成数字到二维矩阵中存储。 { a[i*n + j] = men -'0'; break; } } } } } 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; } cout << endl; } void Test() { int a[N][N] = {}; Pos sp(2, 0); //入口坐标 GetMaze((int*) a, N); PrintMaze((int*)a, N); stack paths; SearchMazePath((int*)a, N, sp, paths); //二维数组实际存储是一维数组,将二维数组强制转换为一维数组传参。 PrintMaze((int*)a, N); } int main() { Test(); system("pause"); return 0; }
有时候,针对迷宫问题,我们还需要求多条路径的最优解(最短路径)。那这时候我们可以用压栈,利用栈帧一层一层压栈的特点实现。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
标题名称:【数据结构】使用栈Stack解决迷宫问题-创新互联
文章转载:http://scyanting.com/article/edheh.html