学懂算法------深度优先搜索（DFS)

vlambda
2020-07-24

学懂算法------深度优先搜索（DFS)

深度优先搜索

深度优先搜索 (DFS, Depth-First Search) 是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直至找到最终的解。例如求解数独，首先在某个格子内填入适当的数字，然后再继续在下一个格子内埴入数字，如此继续下去。如果发现某个格子无解了，就放弃前一个格子上选择的数字，改用其他可行的数字。根据深度优先搜索的特点，采用递归函数实现比较简单。

一、部分和问题

给定整数a1......an,判断能否从中选择出若干个数组成k 深度优先搜索(dfs)


#include<iostream>
using namespace std;
int n,k;
int a[21];
//已经从前i项得到了和sum，然后对于i之后的进行分支
bool dfs(int i, int sum)
{
 //如果前n项都计算过了，则返回sum和k是否相等
 if(i==n) return sum==k;
 //加上a[i]的情况
 if(dfs(i+1,sum+a[i])) return true;
 //不加上a[i]的情况
 if(dfs(i+1,sum)) return true;
 //无论是否加上a[i]都不能凑成k的情况
 return false;
}
int main()
{
 cin>>n;
 int i;
 for(i=0;i<n;i++)
 cin>>a[i];
 cin>>k;
 if(dfs(0,0))
 cout<<"Yes"<<endl;
 else
 cout<<"No"<<endl;
 return 0;

 }

深度优先搜索从最开始的状态出发，遍历所有可以到达的状态。由此可以对所有的状态进行操作，或者列举出所有的状态。

二、Lake Counting

*有一个大小为MN的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里共有多少水洼？（八连通指的是下面图中相对W的*的部分）

限制条件：N,M≤100

输入第一行包含两个正整数 N 和 M，表示将一个园子地面分成N*M块方格，N 行，M列，接下来的 N 行描述了园子地面状况，其中‘W’表示积水的水洼，‘.’表示没有积水。输出仅一个数，表示水洼的总数。输入示例10 12w........ww..www.....www....ww...ww..........ww..........w....w......w...w.w.....ww.w.w.w.....w..w.w......w...w.......w.输出示例3

前面说的情况明确指出是相对的情况，所以并不是说水洼一定要和最开始举例那个一模一样，形式结构上一样也可以算是水洼，接下来我们用dfs即可，从任意的w开始，不停地把邻接的部分用＇．'代替。1次DFS后与初始的这个w连接的所有w就都被替换成了 ' . ', 因此直到图中不再存在w为止，总共进行DFS的次数就是答案了。8个方向共对应了8种状态转移，每个格子作为DFS的参数至多被调用一次，所以复杂度为0(8xNxM)=O(Nx M)。

#include<iostream>
using namespace std;
int N,M;
char field[100][100];
void dfs(int x,int y)
{
 //将现在所在位置替换为.
 field[x][y]='.';
 //循环遍历移动的8个方向
 for(int dx=-1;dx<=1;dx++)
 for(int dy=-1;dy<=1;dy++)
{
  //向x方向移动dx, 向y方向移动dy, 移动的结果为(nx,ny)
  int nx=x+dx;
  int ny=y+dy;
  //判断(nx,ny)是不是在园子内， 以及是否有积水
  if(nx>=0&&nx<=N&&ny>=0&&ny<=M&&field[nx][ny]=='w')
  dfs(nx,ny);
}
}
int main()
{
 cin>>N>>M;
 int i,j;
 int res=0;
 for(i=0;i<N;i++)
 for(j=0;j<M;j++)
 cin>>field[i][j];
 for(i=0;i<N;i++)
 for(j=0;j<M;j++)
 if(field[i][j]=='w')
{
  //从有w的地方开始dfs
  dfs(i,j);
  res++;
}
 cout<<res<<endl;
 return 0; 
}