栈求解迷宫问题

    求迷宫从入口到出口的所有路径是一个经典的程序设计问题。一般的设计思想就是从入口出发，顺着某个方向向下探索，探索分为上下左右四个方位，哪个方向是通的就将向下走，如果每个方向都走不下去就进行原路“回退”。所以需要一个后进先出的结构来保存从入口到出口的路径。所以运用栈来实现是非常方便的，沿着某个方向走，将每个可通的位置进行入栈标记，再切换到下个位置；如果都不通，则栈顶出栈取消标记，再寻找。下来呢就实现一个简单的迷宫求解问题（求解出一条通路就好），至于求解多条通路并且求出最短路径的问题呢我还在进一步的学习中。

    在给出代码之前先来看一下如何动态开辟一个二维数组？

int *a = new int[N*N];
int** a=new int*[N];
//a[i][j] 等价于 a[i*N + j];

    好了，现在来看迷宫的具体实现：

#define _CRT_SECURE_NO_WARNING#pragma once#include#include#includeusing namespace std;#define N 10struct Pos{Pos(size_t row, size_t col):_row(row), _col(col){}int _row;int _col;};void GetMaze(int *a,int n)//读入文件{FILE* fout = fopen("MazeMap.txt", "r");assert(fout);for (int i = 0; i < n; i++){for (int j = 0; j < n;){char ch = fgetc(fout);if ('0' == ch || '1' == ch){a[i*n + j] = ch - '0';j++;}else{continue;}}}fclose(fout);}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;}}bool CheckIsAccess(int* a, int n, Pos next){assert(a);if ((next._row >= 0) && (next._row < n) && (next._col >= 0) && (next._col < n)&&(a[next._row*n+next._col]==0)){return true;}else{return false;}}bool MazePath(int* a, int n, const Pos& entry, stack& path){Pos cur = entry;//入口位置path.push(cur);while (!path.empty()){//是否已经到出口if (cur._row == n - 1){a[cur._row*n + cur._col] = 2;return true;}a[cur._row*n + cur._col] = 2;//*****************************************上Pos next = cur;next._row--;if (CheckIsAccess(a, n, next)){cur = next;path.push(cur);continue;}//*****************************************下next = cur;next._row++;if (CheckIsAccess(a, n, next)){cur = next;path.push(cur);continue;}//*****************************************左next = cur;//左next._col--;if (CheckIsAccess(a, n, next)){cur = next;path.push(cur);continue;}//*****************************************右next = cur;next._col++;if (CheckIsAccess(a, n, next)){cur = next;path.push(cur);continue;}cur = path.top();//到这说明没有通路，所以栈顶出栈path.pop();}return false;}void TestMaze(){int a[N][N] = {};GetMaze((int *)a,N);PrintMaze((int *)a, N);stack path;Pos entry = { 2, 0 };bool ret = MazePath((int *)a, N, entry, path);cout << "是否有通路？" << ret << endl;PrintMaze((int *)a, N);}

当迷宫有多个出口时，利用全局栈可以求得最短路径。这个我们下次再议

本文出自 “Stand out or Get out” 博客，请务必保留此出处http://jiazhenzhen.blog.51cto.com/10781724/1762752