一、問題概述

小時候，我們都玩過走迷宮的游戲吧。看一下這個圖例：

遇到這種問題時，我們第一反應都會先找到迷宮的入口點，然后對上下左右四個方向進行尋跡，

?檢測當前位置是否是通路，是否可以通過，直至找到出口位置，才是迷宮的正確軌跡。如若走到死胡

?同里，則必須返回重新選擇路徑走。

?我們來模擬一下迷宮問題，我們的迷宮是這樣的：

哈哈~雖然有點low！但是可以幫助我們解決實際問題，就將就著看吧，這個更能清晰的說明問題哦。

那么這個迷宮從何而來呢？我將它放在文件中，以讀取文件的方式，將其坐標保存在二維數組中嘍。

二、解決方案

（1）找到入口點（entry），這個由我們自己給定坐標即可。

（2）使用試探法對迷宮尋跡，有上下左右四個方向，將走過的路徑標記一下，將值賦值為其他

? ? ? ? ? ? ? ? ?值。（這里我將它賦為2）

（3）如果走進死胡同里，則采用回溯的思想，將其pop即可。

（4）判斷何時為迷宮出口，當它的橫坐標為（行數-1）時，說明已找到出口。（當然，在這里你

也可以不用規定出口就在最下方，視迷宮的圖例而定）

（5）若迷宮沒有出口，則棧為空。

三、實現代碼

//Maze.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("Maze.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 path)
{if((path._row >= 0 && path._row < 10) && (path._col >= 0 && path._col < 10) && (maze[path._row*n+path._col] == 0)){return true;}return false;
}//棧求解迷宮路徑
void GetMazePath(int *maze,size_t n,Pos entry,stack<Pos>& s)
{Pos cur = entry;Pos next = cur;maze[cur._row*n+cur._col] = 2;s.push(entry);while(!s.empty()){if(s.top()._row  == n-1){return;}//探測上下左右//上next = s.top();next._row-=1;if(IsCheckPath(maze,n,next)){s.push(next);maze[next._row*n+next._col] = 2;continue;}//右next = s.top();next._col+=1;if(IsCheckPath(maze,n,next)){s.push(next);maze[next._row*n+next._col] = 2;continue;}//下next = s.top();next._row+=1;if(IsCheckPath(maze,n,next)){s.push(next);maze[next._row*n+next._col] = 2;continue;}//左next = s.top();next._col-=1;if(IsCheckPath(maze,n,next)){s.push(next);maze[next._row*n+next._col] = 2;continue;}//沒有通路Pos tmp = s.top();maze[tmp._row*n+tmp._col] = 3;s.pop();}
}//遞歸求解迷宮路徑
void GetMazePath(int *maze,size_t n,Pos entry,stack<Pos>& s)
{Pos next = entry;maze[next._row*n+next._col] = 2;s.push(entry);if(next._row == n-1){return;}//探測上下左右//上next = entry;next._row-=1;if(IsCheckPath(maze,n,next)){GetMazePath(maze,n,next,s);}//右next = entry;next._col+=1;if(IsCheckPath(maze,n,next)){GetMazePath(maze,n,next,s);}//下next = entry;next._row+=1;if(IsCheckPath(maze,n,next)){GetMazePath(maze,n,next,s);}//左next = entry;next._col-=1;if(IsCheckPath(maze,n,next)){GetMazePath(maze,n,next,s);}
}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;}
}

//Maze.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Maze.h"//用棧和遞歸實現迷宮問題
const size_t N = 10;void FunTest()
{int Maze[N][N];Pos entry = {2,0};stack<Pos> ss;GetMaze((int*)Maze,N);GetMazePath((int*)Maze,N,entry,ss);cout<<"迷宮是否有出口？"<<!ss.empty()<<endl;PrintMaze((int*)Maze,N);
}int main()
{FunTest();return 0;
}

用棧和遞歸實現普通的迷宮問題還是可以的，但是還有一種這樣的迷宮：

當有多條路徑的時候，就會涉及到路徑長短的問題，到底走哪條路徑會是最優。下篇博客給大家介紹哦。

希望看過此篇博客的編程愛好者提出見解哈。