本文共 2601 字，大约阅读时间需要 8 分钟。
下面是用穷举法来走迷宫
走迷宫的规则：当前坐标是(i, j)下一步可以往四个方向行走，上下左右。
在迷宫数组 0标识可以走，1标识不能走 2 标识已经走过 3标识回退的路
穷举法走出迷宫有两种方法：
1 栈
2 递归
下面通过栈的回溯解决迷宫问题，具体实现如下：
#includeusing namespace std;#include #include #define N 10#define M 11struct Pos{ int _row; int _col;};//获得迷宫void GetMase(int* a){ assert(a); //fout()打开文件,路径（用“\\”）+名字,"r"读取文件 FILE* fout = (FILE*)fopen("E:\\bite\\stack\\MazeMap.txt","r"); assert(fout); for (int i = 0; i < N; i++) { for (int j = 0; j < M;) { char ch = fgetc(fout);//fgetc获得文件中的字符 if (ch >= '0'&&ch <= '9') { a[i*M + j] = ch - '0'; j++; } } }}//判断迷宫是否可以走出去，利用栈存放和回溯实现bool SerachMazePath(int* a, Pos entry, stack & paths){//该迷宫0为通路，1标识为死路,2标识已经走过,3标识回退的路 assert(a); paths.push(entry); while (!paths.empty()) { Pos cur = paths.top(); //走过的标记为2 a[cur._row*M + cur._col] = 2; //检查是否到达出口 if (cur._row == N - 1 || cur._col == M - 1) { return true; } Pos next = cur; //向左走 if (cur._col - 1 >= 0 && a[cur._row*M + cur._col - 1] == 0) { next._col--; paths.push(next); continue; } //向右走 if (cur._col + 1 < M && a[cur._row*M + cur._col + 1] == 0) { next._col++; paths.push(next); continue; } //向上走 if ((cur._row - 1) >= 0 && a[(cur._row - 1) * M + cur._col] == 0) { next._row--; paths.push(next); continue; } //向下走 if (cur._row + 1
递归实现如下：
//判断迷宫是否可以走出去，利用递归实现//递归的实现相比较栈减少在回溯时的重复比较，但递归会一直回退到入口处结束int SerachMazePath(int* a,Pos entry){//该迷宫0为通路，1标识为死路,2标识已经走过,3标识回退的路 assert(a); Pos cur = entry; //走过的标记为2 a[cur._row*M + cur._col] = 2; Pos next = cur; //检查是否到达出口 if (cur._row != N - 1 && cur._col != M - 1) { //向左走 if (cur._col - 1 >= 0 && a[cur._row*M + cur._col - 1] == 0) { next = cur; next._col--; if(SerachMazePath(a, next)) return 1; a[next._row*M + next._col] = 3; } //向右走 if (cur._col + 1 < M && a[cur._row*M + cur._col + 1] == 0) { next = cur; next._col++; if(SerachMazePath(a, next)) return 1; a[next._row*M + next._col] = 3; } //向上走 if ((cur._row - 1)>=0 && a[(cur._row - 1) * M + cur._col] == 0) { next = cur; next._row--; if(SerachMazePath(a, next)) return 1; a[next._row*M + next._col] = 3; } //向下走 if (cur._row + 1 测试用例如下：
void Test1(){ int *sm = new int[N * M]; Pos entry; stack paths; entry._row = 2; //迷宫入口处 entry._col = 0; GetMase(sm); cout << "是否找到通路：" << SerachMazePath(sm, entry, paths) << endl; Print(sm);}void Test2(){ int *sm = new int[N * M]; Pos entry; entry._row = 2; //迷宫入口处 entry._col = 0; GetMase(sm); Print(sm); cout << "是否找到通路：" << SerachMazePath(sm, entry) << endl; Print(sm);} 结果如下所示：
本文出自 “” 博客，请务必保留此出处
转载地址：http://jilbi.baihongyu.com/