/* 迷宫的递归解法 比栈解法清爽的多了 DFS小应用 总体思想 DFS+条件回溯 */ #include<iostream> #include<string> #include<cstring> #define N 30 using namespace std; int m,n,find,dir[4][2]={0,1,0,-1,1,0,-1,0};//转向控制数组 string map[N]; bool legal(int i,int j)//判断当前位置是否合法 { if(i>=0&&i<m&&j>=0&&j<n) return true; return false; } void DFS(int x,int y)//核心函数 { map[x][y]='o';//记录路径 if(x==m-1&&y==n-1)//找到的话标记find为找到 {find=1;return;} for(int i=0;i<4;i++)//探索四个方向 { int sx=x+dir[i][0],sy=y+dir[i][1]; if(legal(sx,sy)&&map[sx][sy]=='_') { DFS(sx,sy); if(!find)//根据情况进行反标记 map[sx][sy]='_';//未找到就反标记 else//找到的话就直接返回保存路径 return; } } } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); cout<<"请按下列格式输入迷宫："<<endl <<"1. '#'代表墙'_'代表可走路径"<<endl <<"2. 不用输入边框"<<endl <<"3. 默认为左上角为入口右下角为出口"<<endl; m=0; while(getline(cin,map[m])) m++; n=map[0].size();//得到迷宫的长和宽 if(map[0][0]=='#'||map[m-1][n-1]=='#')//特殊情况处理 {cout<<"No Solution !"<<endl;return 0;} find=0;//标志 DFS(0,0);//从左上角开始搜索路径 if(find)//找到路径情况 { cout<<endl<<"一个可能的解法为:"<<endl<<endl; for(int i=0;i<m;i++) { cout<<map[i]<<endl; } } else//未找到路径 cout<<"No Solution !"<<endl; return 0; }