DFS（深度优先优先搜索）
基本内容：深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法
简单而言就是从一个点开始搜索，如果面对面对分支，则按照某种顺序选择分支进入，直到到达死路，则向上返回，进行下一次选择最后将所有的路线完全遍历的搜索方法

一：实现方法：
栈或者用递归模拟栈 循环模拟递归
下面为各种方法的模板

  • 1.1递归实现dfs

    int dfs(int t)
{
if(满足输出条件)
{
输出解;
}
else
{
for(int i=1;i<=尝试方法数;i++)
if(满足进一步搜索条件)
{
为进一步搜索所需要的状态打上标记;
dfs(t-1);
恢复到打标记前的状态;//也就是说的{回溯一步}
}
}
}

  • 1.2循环模拟递归实现dfs

    void dfs(int n)
{
while(满足标记条件的数据)
{
标记这些数据
数据变化（n-1）
}
对标记进行判定，进行分类
return;
}
int main（）
{
xxx
对用不同标记的数据进行计算，分析
}

  • 1.3栈实现dfs

    void dfs(int n)
{
  stackst;
  xxx; 
  while(遍历所有数据)
  {
      if(满足出栈条件)
      {
          对数据处理，标记 ,计算 
       } 
       else 入栈
  } 
  return; 
}

二：常见题型与处理方法
2.1 寻找某个节点的路径
2.11走迷宫，走地图的类型

  1. 扫雷游戏

图片说明

下面用两种方法来处理这个问题
1递归法：

int dfs(int a,int b,int t)
{
    if(t==8)
    {
        return 0;
    }
    else{
        if(mp[a+x[t]][b+y[t]]==-1)
        return dfs(a,b,t+1)+1;
        else return dfs(a,b,t+1);
    }
}

  • 2循环模拟法

    int dfs(int a,int b)
{
  int ant=0;
  if(mp[a][b]==-1)
  return -1;
  else {
      for(int i=0;i<8;i++)
      {
          if(a+x[i]>=1&&a+x[i]=1&&b+y[i]<=n&&mp[a+x[i]][b+y[i]]==-1)
          ant++;
      }
      return ant;
  }
}

  • 主函数

    #include
using namespace std;
const int maxn=110;
int m,n;
char temp;
int mp[maxn][maxn];
int x[8]={-1,-1,-1,0,1,1,1,0};
int y[8]={1,0,-1,-1,-1,0,1,1};
//这里放函数部分
int main()
{
   scanf("%d%d",&m,&n);
   getchar();
   for(int i=1;i<=m;i++)
   {
       for(int j=1;j<=n;j++)
       {
           scanf("%c",&temp);
           if(temp=='*')
           mp[i][j]=-1;
           else mp[i][j]=0;
       }
   getchar();
   }
   for(int i=1;i<=m;i++)
   {
       for(int j=1;j<=n;j++)
       {
           if(mp[i][j]!=-1)
           {
               mp[i][j]=dfs(i,j,0);
           }
       }
   }
   for(int i=1;i<=m;i++)
   {
       for(int j=1;j<=n;j++)
       {
           if(mp[i][j]==-1)printf("*");
           else printf("%d",mp[i][j]);
       }
       printf("\n");
   }
   return 0;
}

2.迷宫
图片说明

  • 1递归法：
    #include
using namespace std;
int vis[10][10];//构建走过的路的标记
int a[10][10]; //构建地图
int n,m,sx,sy,fx,fy,sum,res;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};//通过两个一维数组实现转向
void dfs(int x,int y)//递归实现dfs搜索
{
  if(x==fx&&fy==y)
  {
      res++;
      return;
  }//递归出口
  vis[x][y]=1;//走过的路标记
  for(int i=0;i<4;i++)//循环遍历四种方向
  {
      int tx=x+dx[i],ty=y+dy[i];
      if(txn||ty>m||vis[tx][ty]||a[x][y]) continue;
      dfs(tx,ty);//递归搜索
      vis[tx][ty]=0;//搜索结束将路径还原
   } 
   vis[x][y]=0;//路径还原
}
int main()
{
  scanf("%d%d%d",&m,&n,&sum);
  scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
  while(sum--)
  {
      int x,y;
      scanf("%d%d",&x,&y);
      a[x][y]=1;
  }
  if(a[fx][fy]==1)
  {
      printf("0\n");
   } 
   else {
       dfs(sx,sy);
       printf("%d\n",res);
   }
  return 0;    
}

2.2 DFS在图的问题里的应用