/* (一)初级迷宫问题: 0:代表通 1:代表不通 求迷宫的通路 (二)步骤: 1.创建迷宫 * 从文件中读取迷宫 * 开辟二维数组存放迷宫 2.寻找通路 * 检查某位置是否为通 * 出口位置判断 * 走过的路用2标记 * 利用栈回溯 (三)问题 1.解决回溯中重复探测:递归 2.最优解:迷宫的最短通路 */ #include#include #include #include #define _CRT_SECURE_NO_WARNINGS 1 #define N 10 using namespace std; struct Pos { size_t _row; //行 size_t _col; //列 }; void GetMap(int* m, int n) { int i = 0; int j = 0; assert(m); FILE* fin = fopen("C:\\学习\\code\\数据结构\\MazeMap\\MazeMap.txt","r"); assert(fin); for(i = 0; i < n; i++) { for(j = 0; j < n;) { char ch = fgetc(fin); if(ch == '0'||ch == '1') { m[i*n+j] = ch - '0'; j++; } } } } void PrintMap(int* m, int n) { assert(m); int i = 0; int j = 0; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { cout< = 0 && next._row < n && next._col >= 0 && next._col < n && m[next._row*n+next._col] == 0) { return true; } else { return false; } } bool SearchMazePath(int* m, int n, Pos enrty,stack paths) { assert(m); paths.push(enrty); while(!paths.empty()) { Pos cur = paths.top(); m[cur._row * n + cur._col] = 2; //检查是否找到出口 if(cur._row == n-1) { return true; } Pos next = cur; //上 next._row--; if(CheckIsAccess(m, n, next)) { paths.push(next); continue; } next = cur; //右 next._col++; if(CheckIsAccess(m, n, next)) { paths.push(next); continue; } next = cur; //next归位 //下 next._row++; if(CheckIsAccess(m, n, next)) { paths.push(next); continue; } next = cur; //左 next._col--; if(CheckIsAccess(m, n, next)) { paths.push(next); continue; } paths.pop(); } return false; } int main() { int map[N][N]= {0}; GetMap((int*)map, N); PrintMap((int*)map, N); Pos enrty = {2,0}; stack paths; cout<
文章题目:初级版迷宫问题(栈的应用)
文章起源:http://cdkjz.cn/article/pgophi.html