dfs深度查询

dfs深度优先搜索

一条路走到头，在回溯走别的路

经典的走迷宫问题代码如下

#include<bits/stdc++.h> using namespace std; int p,q; int mins=1e9; int a[100][100]; int v[100][100]; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; void dfs(int x,int y,int step) { if(x==p&&y==q) { if(step<mins) { mins=step; return; } } for(int i=0;i<4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(a[nx][ny]==1&&v[nx][ny]==0) { v[nx][ny]=1; dfs(nx,ny,step+1); v[nx][ny]=0; } } return; } int main() { int stratx,straty; int m,n; cin>>m>>n; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; } } cin>>stratx>>straty>>p>>q; v[stratx][straty]=1; dfs(stratx,straty,0); cout<<mins<<endl; return 0; }

从中我们可以看出这是一个递归，从（stratx,straty)坐标开始用dfs找，如果下一个坐标可以走且未被标记，那么就标记这个坐标，继续dfs，如果不能走，就回溯到上一步，取消标记，像其他三个方向查找，最终找到终点，记录步数。

注：

dx[4]={1,-1,0,0}

dy[4]={0,0,1,-1}

这是表示坐标的上下左右四个方向