dfs的模板

不知不觉开学两周了。。。 嗯。。 迷迷糊糊的看了几天的算法,尤其是深搜方面的,刷了不少的题,总觉的是时候在去巩固一下深搜的基本思路了

深搜的本质就是围绕着两方面去写代码,第一步是当前做什么?下一步是做什么?围绕着两方面可以则可以得出dfs的基本模板

void dfs(step)

  { if(判断是否到达搜索的终点)

​     if(判断数据是否越界)

for()

​     //做下一步的事

dfs(step+1)

}

两道例题

凑数字

从1-9的数字中选取出不同的数字组合,使得其可以组合成口口口+口口口=口口口

这题可以用几个for循环暴力嵌套,但是搜索比起来思路更清晰

假设你 手中有 1–9号的扑克牌 将这九张扑克牌放入九个容器中 使得 口口口+口口口=口口口 成立 有多少种解法*

  include<stdio.h>
  int a[10]; *//放入扑克牌的箱子*

  int book[10]; *//扑克牌*

  int total=0;  *//解法*





  void dfs(int *step*)

  {  int i;

    if(*step*==10)

  ​    {

  ​      if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])

  ​       { total++;

  ​        printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9] );}

  ​       return ;

  ​    }

  ​       

  ​    for(int i=1;i<=9;i++) *//从第一个箱子开始  可以放入1---9号的扑克牌* 

  ​      {

  ​         if(book[i]==0)

  ​           {

  ​              a[*step*]=i;

  ​               book[i]=1;

  ​           

  ​          dfs(*step*+1);



  ​            book[i]=0;  //用完的数字取消标记

  ​           }

  ​      }

  return;

  } 





  int main()

  { dfs(1);

    printf("total=%d",total/2);

    getchar();







  return 0;

  }

走迷宫

高桥先生住的小区是长方形的,被划分成一个个格子。高桥先生想从家里去鱼店,高桥先生每次可以走到他前后左右四个格子中的其中一个,但不能斜着走,也不能走出小区。

现在给出地图:

s:代表高桥先生的家

g:代表鱼店

.:代表道路

#:代表墙壁

高桥先生不能穿过墙壁。

输入:第一行输入n(1<=n<=500),m(1<=m<=500)代表小区的长和宽,接下来n行每行m个字符,描述小区中的每个格子。

输出:如果高桥先生能到达鱼店,输出”Yes”,否则输出”No”。

  #include<cstdio>

  #include<iostream>

  #include<algorithm>

  #include<cstring>

  #include<string>

  using namespace std;



  const int N=510;

  char Map[N][N];  *//定义地图*

  bool jud[N][N];  *//定义地图的每个点是否可以到达*

  int sx, sy;

  int ex, ey;

  int vis[N][N];

  int n,m;



  int Move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};



  void dfs(int *x*,int *y*)

  {   vis[*x*][*y*]=1;

    int nx,ny;



  ​    for(int i=0;i<4;i++)

  ​     {  

  ​       nx=*x*+Move[i][0];

  ​       ny=*y*+Move[i][1];

  ​        if(nx<1||ny<1||nx>n||ny>m) continue;

  ​          if(Map[nx][ny]!='#'&&(vis[nx][ny]!=1))

  ​            dfs(nx,ny);

  ​     }

  ​    





  }

  int main()

  {  

  ​    cin>>n>>m;

  ​    for(int i=1;i<=n;i++)

  ​      for(int j=1;j<=m;j++)

  ​        { cin>>Map[i][j];

  ​           if(Map[i][j]=='s')

  ​             {sx=i;

  ​             sy=j;}

  ​           if(Map[i][j]=='g')

  ​            {

  ​              ex=i;

  ​              ey=j;

  ​            }  





  ​        }

    dfs(sx,sy);

    if(vis[ex][ey]==1)

  ​     {

  ​       cout<<"yes";

  ​     }

  ​    else

  ​    {

  ​      cout<<"no";

  ​    }

  ​    





  }