深搜算法 经典题目 一 密宫 问题描述 从S出发 到达终点T 只能走“ . ” "*"不能走 走过的路用m替换 输入格式
5 6 ....S* .***.. .*..*. *.***. .T....输出格式
....m* .***mm .*..*m *.***m .Tmmmm基本思路 按照逆时针的路线走 上左下右的方式走 走不通了原路返回 继续换个方向走 直到走到终点为止 递归 回溯 深搜的算法思想 代码如下
#include< iostream> #include< string> using namespace std; int n,m,tx,ty; string maze[110]; //二维数组 bool vis[105][105];//标记函数 bool in(int x,int y) //判断坐标是否越界 { return 0<=x&&x<n&&0<=y&&y<m; } bool dfs(int x,int y) //搜索查找函数 { if(maze[x][y]=='T') { return true; } vis[x][y]=1; //标记已经走过的路 maze[x][y]='m'; //从此处（m处）开始走 tx=x-1,ty=y; //向上走 然后继续深搜 直到走出迷宫 if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]) { if( dfs(tx,ty)) { return true; } } tx=x,ty=y-1; //向左走 然后继续深搜 直到走出迷宫 if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]) { if( dfs(tx,ty)) { return true; } } tx=x+1,ty=y; //向下走 然后继续深搜 直到走出迷宫 if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]) { if( dfs(tx,ty)) { return true; } } tx=x,ty=y+1; //向右走 然后继续深搜 直到走出迷宫 if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]) { if( dfs(tx,ty)) { return true; } } vis[x][y]=0; //若真的走不出去 这里是否标记无所谓 maze[x][y]='.'; //若真的走不出去 此时取消标记 return false; } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>maze[i]; } int x,y; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(maze[i][j]=='S') { x=i;y=j; } } } cout<<endl; if(dfs(x,y)) { for(int i=0;i<n;i++) {cout<<maze[i]<<endl;} }//此时的maze[i]就是 maze[i][j] else { cout<<"NO!"<<endl; } return 0; }优化方案 四个方向可以数组循环的方式写 //方法二 代码优化 将搜索函数优化
#include< iostream> #include< string> using namespace std; int n,m; string maze[110]; //二维数组 bool vis[105][105];//标记函数 int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; bool in(int x,int y) //判断坐标是否越界 { return 0<=x&&x<n&&0<=y&&y<m; } bool dfs(int x,int y) //搜索查找函数 { if(maze[x][y]=='T'){ return true; } vis[x][y]=1; //标记数组 maze[x][y]='m'; //将能走过的路 都标记为m for(int i=0;i<4;i++) { int tx=x+dir[i][0]; int ty=y+dir[i][1]; if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){ if(dfs(tx,ty)) { return true; } } } maze[x][y]='.'; //走不通的路 虽然已经标记为”m“ 需要还原 取消标记 vis[x][y]=0; // return false; }