有一个二维迷宫，n行m列，‘s’表示迷宫的起点，‘T’表示迷宫的终点，‘#’表示围墙，‘.’表示通路。现在从S出发，你不能穿墙，问你能否到达终点，若能将路线打印出来，若不能打印“no”
输入：
第一行输入n，m（1<n,m<1000）
接下来输入n行，每行m列的迷宫
输出：
输出迷宫路线，或“no”；
#include <iostream> #include <string> using namespace std; bool b[105][105]; string a[105]; int n,m; bool in(int x,int y){ return x>=0 && x<n && y>=0 && y<m; } bool dfs(int x,int y){ int tx,ty; //判断是否到达整点 if(a[x][y]=='t'){ return true; } //b用来标记是否遍历，a用来标记路线 b[x][y]=1; a[x][y]='+'; //接下来四个转向 tx=x-1; ty=y; if(in(tx,ty) && a[tx][ty]!='*' && !b[tx][ty]){ if(dfs(tx,ty)){ return true; } } tx=x; ty=y-1; if(in(tx,ty) && a[tx][ty]!='*' && !b[tx][ty]){ if(dfs(tx,ty)){ return true; } } tx=x+1; ty=y; if(in(tx,ty) && a[tx][ty]!='*' && !b[tx][ty]){ if(dfs(tx,ty)){ return true; } } tx=x; ty=y+1; if(in(tx,ty) && a[tx][ty]!='*' && !b[tx][ty]){ if(dfs(tx,ty)){ return true; } } b[x][y]=0; a[x][y]='.'; return false; } int main(){ int x,y; cin>>n>>m; //输入迷宫 for(int i=0;i<n;i++){ cin>>a[i]; } //寻找起始点s for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='s'){ x=i; y=j; } } } cout<<"---------------"<<endl; //判断是否有正确路线 if(dfs(x,y)){ for(int i=0;i<n;i++){ cout<<a[i]<<endl; } } else{ cout<<"no"; } return 0; }
运行结果如下：
该方法代码冗杂，其四个移动方向可以用一个循环代替：
#include <iostream> #include <string> using namespace std; bool b[105][105]; string a[105]; int e[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; int n,m; bool in(int x,int y){ return x>=0 && x<n && y>=0 && y<m; } bool dfs(int x,int y){ int tx,ty; if(a[x][y]=='t'){ return true; } b[x][y]=1; a[x][y]='+'; for(int i=0;i<4;i++){ tx=x+e[i][0]; ty=y+e[i][1]; if(in(tx,ty) && a[tx][ty]!='*' && !b[tx][ty]){ if(dfs(tx,ty)){ return true; } } } b[x][y]=0; a[x][y]='.'; return false; } int main(){ int x,y; cin>>n>>m; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='s'){ x=i; y=j; } } } cout<<"---------------"<<endl; if(dfs(x,y)){ for(int i=0;i<n;i++){ cout<<a[i]<<endl; } } else{ cout<<"no"; } return 0; }
整两中本质是一样的，因此时间复杂度都是一样的，但后者代码量少一些。
