前言：

我的地图文件（MazeMap.txt）如下：

size:(a,a)1111111111111111111100011111111101111111110111111111011111111100000011110111101111011110111101111011

下面的pos类用来保存某个位置的坐标

GetMaze函数用来判断地图格式的合法性，若合法则读取地图内容，并将内容存入参数arr所指向的内存中。

structpos{pos(introw=0,intcol=0):_row(row),_col(col){}int_row;int_col;};voidGetMaze(int*&arr,int&sz,int&row,int&col){FILE*fout=fopen("MazeMap.txt","r");assert(fout);char*title=newchar[40];title=fgets(title,7,fout);if(strcmp(title,"size:(")){cout<<"地图文件错误！"<<endl;throw1;}row=fgetc(fout)-87;title=fgets(title,2,fout);if(strcmp(title,",")){cout<<"地图文件错误！"<<endl;throw1;}col=fgetc(fout)-87;arr=newint[row*col];sz=row*col;title=fgets(title,2,fout);for(inti=0;i<sz;i){charch=fgetc(fout);if(ch!=''&&ch!='\n'&&ch!='\0'){*(arr+i)=ch-'0';i++;}}}

一、找到出口

boolMazePath(int*arr,intn,constpos&entry,stack<pos>&path)//假设下边沿为迷宫的出口{poscur=entry;path.push(cur);while(!path.empty()){*(arr+n*(cur._row)+cur._col)=2;if(cur._row==n-1){returntrue;}//向下if((cur._row+1<10)&&(*(arr+n*(cur._row+1)+cur._col)==0)){*(arr+n*(cur._row+1)+cur._col)=2;++cur._row;path.push(cur);continue;}//向上if((cur._row-1>=0)&&(*(arr+n*(cur._row-1)+cur._col)==0)){*(arr+n*(cur._row-1)+cur._col)=2;--cur._row;path.push(cur);continue;}//向左if((cur._col-1>=0)&&(*(arr+n*cur._row+cur._col-1)==0)){*(arr+n*cur._row+cur._col-1)=2;--cur._col;path.push(cur);continue;}//向右if((cur._col+1<10)&&(*(arr+n*cur._row+cur._col+1)==0)){*(arr+n*cur._row+cur._col+1)=2;++cur._col;path.push(cur);continue;}//走不通cur._col=path.top()._col;cur._row=path.top()._row;path.pop();}}

二、找到所有出口并得出最短路线（最优解）

template<typenameT>voidClearPath(stack<T>&stack){while(!stack.empty()){stack.pop();}}staticvoidSaveBestPath(stack<pos>&path,vector<stack<pos>>path_vec){stack<pos>best_path;intsz=(path_vec.back()).size();best_path=path_vec.back();while(!path_vec.empty()){if(sz>(path_vec.front()).size()){best_path=path_vec.front();}path_vec.pop_back();}path=best_path;}staticstructExit{Exit(introw,intcol):_row(row),_col(col){}int_row;int_col;};//堵住已知的出口(为了不销毁数据，不使用引用)staticvoidBlockKnownExit(int*arr,vector<Exit>exit_vec,intn){Exitext1=exit_vec.back();while(!exit_vec.empty()){ext1=exit_vec.back();*(arr+n*ext1._row+ext1._col)=3;exit_vec.pop_back();}}//假设下边沿为迷宫的出口boolMazePathMin(int*arr,intn,constpos&entry,stack<pos>&path){vector<stack<pos>>path_vec;//用于存放所有的路径vector<Exit>exit_vec;//用于存储所有出口poscur=entry;path.push(cur);while(!path.empty()){*(arr+n*(cur._row)+cur._col)=2;if(cur._row==n-1){//找到一个出口*(arr+n*(cur._row)+cur._col)=3;Exitext_tmp(cur._row,cur._col);path_vec.push_back(path);exit_vec.push_back(ext_tmp);//清空路径，寻找除该出口外的其他出口ClearPath(path);GetMaze(arr,n);BlockKnownExit(arr,exit_vec,n);cur=entry;path.push(cur);}//向下if((cur._row+1<10)&&(*(arr+n*(cur._row+1)+cur._col)==0)){*(arr+n*(cur._row+1)+cur._col)=2;++cur._row;path.push(cur);continue;}//向上if((cur._row-1>=0)&&(*(arr+n*(cur._row-1)+cur._col)==0)){*(arr+n*(cur._row-1)+cur._col)=2;--cur._row;path.push(cur);continue;}//向左if((cur._col-1>=0)&&(*(arr+n*cur._row+cur._col-1)==0)){*(arr+n*cur._row+cur._col-1)=2;--cur._col;path.push(cur);continue;}//向右if((cur._col+1<10)&&(*(arr+n*cur._row+cur._col+1)==0)){*(arr+n*cur._row+cur._col+1)=2;++cur._col;path.push(cur);continue;}//走不通的时候：cur._col=path.top()._col;cur._row=path.top()._row;path.pop();}//path为空SaveBestPath(path,path_vec);//把最佳的路径保存进path中（仍然倒序）return(!path.empty());}

三、优化后的算法

四、用递归实现

//待续