深度优先搜索（DFS）

简述

深度优先搜索的英文简写是DFS(Depth First Search)，属于图论中搜索算法中的一种，它所遵循的搜索策略是尽可能“深”地搜索图。下面我们通过一个小例子来认识什么是DFS。

我们观察如下这个无向图

我们从A点发起深度优先搜索，我们设A点是1号点，B点是2号点，同理：C是3、D是4、E是5、F是6。我们用一个q数组来记录我们访问的顺序，q[i]=j代表我们访问的第i个节点是第j号节点。由于我们从A点开始进行DFS，所以q[1]=1，对吧？接下来，我们可以走A点相连的点，也就是B点或者D点(假设我们先走B点，这个顺序可以变),那么q[2]=2，走到B点之后发现和B点相连的点都走过了，这时，我们进行DFS最重要的一步：回溯，我们返回刚才走过的A点，发现A点相连的点还有D点没走，于是我们走到了D点，也就是q[3]=4，D点相连的没有走过的点有C和E，我们考虑先走C点，得到q[4]=3，这时发现C点相连的点我们也都走过了，回溯到上一节点：D点，发现D点周围还有没访问的节点，于是我们走到了E点，同时更新q数组，得到q[5]=5，然后继续走E周围没有走过的点：F点，得到q[6]=6，于是我们得到了入下的q数组：

• q[1]=1;
• q[2]=2;
• q[3]=4;
• q[4]=3;
• q[5]=5;
• q[6]=6;
  

也就是说,我们通过从A点进行DFS，遍历整个图所经过节点的顺序是：A、B、D、C、E、F。但是这并不是唯一的答案，从A点开始DFS还有可能是如下结果：

• ADCEFB
• ADEFCB
• ABDEFC
  

至于为什么，大家动脑想一下，很容易想到。

模版

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=100;
bool vst[maxn][maxn]; // 访问标记
int map[maxn][maxn]; // 坐标范围
int dir[4][2]= {0,1,0,-1,1,0,-1,0}; // 方向向量，(x,y)周围的四个方向
bool CheckEdge(int x,int y) // 边界条件和约束条件的判断
{
    if(!vst[x][y] && ...) // 满足条件
        return 1;
    else // 与约束条件冲突
        return 0;
}

void dfs(int x,int y)
{
    vst[x][y]=1; // 标记该节点被访问过
    if(map[x][y]==G) // 出现目标态G
    {
        ...... // 做相应处理
        return;
    }
    for(int i=0; i<4; i++)
    {
        if(CheckEdge(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点
            dfs(x+dir[i][0],y+dir[i][1]);
    }
    return; // 没有下层搜索节点，回溯
}

int main()
{
    ......
    return 0;
}

例题

例题1.hrbust 1143

题意：有一个泉眼，由于当地的地势不均匀，有高有低，这个泉眼不断的向外溶出水来，这意味着这里在不久的将来将会一个小湖。水往低处流，凡是比泉眼地势低或者等于的地方都会被水淹没，地势高的地方水不会越过。而且又因为泉水比较弱，当所有地势低的 地方被淹没后，水位将不会上涨，一直定在跟泉眼一样的水位上。 所有的地图都是一个矩形，并按照坐标系分成了一个个小方格，Leyni知道每个方格的具体高度。我们假定当水留到地图边界时，不会留出地图外，现在他想通过这些数据分析出，将来这里将会出现一个多大面积的湖
要求：Time Limit: 1000 MS , Memory Limit: 65536 K
思路：

• 可以枚举么？
• 枚举的话，首先该位置的高度必须低于泉眼，可是低于泉眼的地方一定可以被淹没么？不一定！
• 例如(1,5)那个位置处高度为1，但是“四面环山”，水进不来！所以还必须满足该点到达泉眼存在一条路径使得整条路径上的最高高度<=泉眼。
• 怎么做呢？
• DFS！
• 从起点开始DFS，找到所有DFS能够经过的点，个数便是答案！

#include <stdio.h>
#include <string.h>
bool used[1005][1005];
int a[1005][1005],n,m,p,q;
int ans;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){
   // printf("(%d,%d)\n",x,y);
    used[x][y]=1;
    ans++;
    for(int k=0;k<4;k++){
        int tx=x+dx[k],ty=y+dy[k];
        if (tx>0&&ty>0&&tx<=n&&ty<=m&&!used[tx][ty]&&a[tx][ty]<=a[p][q]){
            dfs(tx,ty);
        }
    }
}
int main(){
    while(scanf("%d%d%d%d",&n,&m,&p,&q)!=EOF){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        ans=0;
        memset(used,0,sizeof(used));
        dfs(p,q);
        printf("%d\n",ans);
    }
}