一、问题概述
之前，我们了解了如何实现迷宫问题（对于迷宫只有一个出口可以通的情况），事实上我们的迷宫有多个出口，对于每条路径来说，有长有短，所以在这里，我们讨论一下迷宫的最短路径，即迷宫路径的最优解问题。
二、解决方案
对于这样一个迷宫：
注：数字为0的表示可以通过，数字为1的表示不可以通过。
从入口坐标：（2，0）开始，可以到达出口位置的通路总共有三条。可想而知，肯定得把每一条路径都得遍历一遍，记录每条路径的长度。我们这里采用了递归的思想。
求解最短路径的办法：
（1）将入口点标记起来，给其赋值；
（2）每次访问的下一个位置就是前一个位置的值+1，直至一条路径成功通往出口；
（3）如果访问下一条路径的时候，递归会回退，在这里回退时它还会检测是否有通路，（上上节讲迷宫问题时有具体实现，可以去参照），这时由于我们赋的值已经改变了，所以此时判断的条件为如果它的下一个位置的值+1>当前的位置的值，它就可以通过。
（4）当每条路径走完后，会显示最后出口的值，这样就知道哪条路径最短啦。
图示如下：
三、实现代码
//Maze1.h
#include<iostream> using namespace std; #include<assert.h> #include<stack> struct Pos { int _row; int _col; }; void GetMaze(int *Maze,size_t N) { FILE* fout = fopen("Maze1.txt","r"); assert(fout); for(size_t i = 0; i < N; ++i) { for(size_t j = 0; j < N; ) { int value = fgetc(fout); if(value == '1' || value == '0') { Maze[i*N+j] = value - '0'; ++j; } else if(value == EOF) { cout<<"Maze error!"<<endl; return; } } } } bool IsCheckPath(int *maze,size_t n,Pos cur,Pos next) { if((next._row < 0 || next._row >= 10) || (next._col < 0 || next._col >= 10) ||(maze[next._row*n+next._col] == 1)) { return false; } if(maze[next._row*n+next._col] == 0) { return true; } return maze[next._row*n+next._col]+1 > maze[cur._row*n+cur._col]; } //递归 void GetMazePath(int *maze,size_t n,Pos entry,stack<Pos>& s,stack<Pos>& ss) { Pos cur; Pos next; s.push(entry); next = entry; if(entry._row == n-1) { if(ss.empty() || s.size() < ss.size()) { ss = s; } s.pop(); return; } //探测上下左右 //上 next = entry; cur = next; next._row-=1; if(IsCheckPath(maze,n,cur,next)) { maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1; GetMazePath(maze,n,next,s,ss); } //右 next = entry; cur = next; next._col+=1; if(IsCheckPath(maze,n,cur,next)) { maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1; GetMazePath(maze,n,next,s,ss); } //下 next = entry; cur = next; next._row+=1; if(IsCheckPath(maze,n,cur,next)) { maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1; GetMazePath(maze,n,next,s,ss); } //左 next = entry; cur = next; next._col-=1; if(IsCheckPath(maze,n,cur,next)) { maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1; GetMazePath(maze,n,next,s,ss); } //四方都不通 s.pop(); } void PrintMaze(int *maze,size_t n) { cout<<"迷宫显示:>"<<endl; for(size_t i = 0; i < n; ++i) { for(size_t j = 0; j < n; ++j) { cout<<maze[i*n+j]<<" "; } cout<<endl; } } //Maze1.cpp
#include"Maze1.h" //用栈和递归实现迷宫问题 const size_t N = 10; void FunTest() { int Maze[N][N]; Pos entry = {2,0}; stack<Pos> ss; stack<Pos> ss1; GetMaze((int*)Maze,N); Maze[entry._row][entry._col] = 2; GetMazePath((int*)Maze,N,entry,ss,ss1); cout<<"迷宫是否有出口？"<<!ss.empty()<<endl; PrintMaze((int*)Maze,N); } int main() { FunTest(); return 0; } 四、运行结果
