dfs习题讲解

概述

在我看来，每种算法都由两个部分组成，一部分是思想，另外一部分就是实现能力，二者缺一不可。缺少思想，算法就无法站住，或者可以说固定的模板无法和灵活的题目相联系。缺少实现能力，算法就成了空中楼阁，你想到的思路再清晰再高明，打不出来终究是心有余力不足。

在这篇博客中我将根据具体例题讲解部分dfs思路，正如上面所说，思想和实现能力是相辅相成的，我在这里理清了思路，还需要进行一个系列题目的练习，才能说把思路巩固了。如果有能力再进行高级的练习以及对于题目变形的解答。我希望在讲解的过程中也可以教学相长，如有错漏还请不吝赐教。

正文（例题）

HDU 2553 N皇后问题

n皇后问题就是最经典的dfs问题，一般的n皇后问题主要求解的是解的个数或者摆放的位置图。

题目

http://acm.hdu.edu.cn/showproblem.php?pid=2553

思路

我对思路的讲解将以八皇后为例子，即n取8时的思路。

首先，画出一个8*8的表格。

据题意可知，对于某一个点是否可以放置皇后的条件是同行同列或者一条斜线上不存在皇后。

我们从第一个点即[1][1]开始试图放置，由于同行同列以及一条斜线均无皇后（下称条件），故在[1][1]处放置皇后。

而在此时，按照普通的搜索方式，应该从[1][2]试图放置。但很明显[1][1]与[1][2]同处一行，违背了条件，可知一旦在该行放置了皇后就应该跳到下一行进行搜索，以减小时间复杂度。根据这些特性，我们可以规定棋盘的每一行为一层，进行不断的递归操作来遍历，这就是dfs的大概形式。

正如上段所说，第一行已经放置了皇后，搜索通过递归跳到了第二层，也就是第二行中。在第一个位置即[2][1]进行判断。由于第一列中已有皇后放置（[1][1]），故判断下一个位置[2][2]，由于同一斜线存在皇后（[1][1]），不满足条件故判断下一个位置[2][3]，发现满足条件，将第二行的皇后放置在第三列。

第二行也已经放置了皇后，通过递归跳到第三行，很明显第三行首先放在第五列，即[3][5]处。

dfs到达了第四层，第一列的位置由于已经放置了皇后（[1][1]），故跳过。[4][2]这个位置满足条件，故将皇后放置在此处。

据此规则判断出第五行放置在第四列即[5][4]处。

dfs到达第六层，可知前五列均无法放置皇后，而后三列也均由于前三行与其同处一条斜线上而不满足条件，如此第六行在当前状态没有满足条件的位置。故dfs进行回溯操作，dfs回溯至第五层。

在第五行的当前位置也即[5][4]处已被证明不行，则在下一个位置尝试即[5][5]，当然由于[3][5]与该位置处于同一列，不满足条件。在[5][6]和[5][7]都因为条件不满足而跳到下个位置，在[5][8]这个位置当前可行，则尝试该位置。

在第六行所有位置仍然均不满足条件，如此回溯到第五层，然而第五层已经到了最后一个位置，如此回溯第四层，尝试[4][7]这个位置。

通过各种尝试，得出第一种情况。

所有摆放情况都尝试过之后，总共有92种情况。

代码

下面放出我针对hdu2553 N皇后问题打出的代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
int sum=0,i,j;
int num[15]={0};
int q;
int lie[15];
int t;
bool pd(int m,int o)
{
    for(j=1;j<=m-1;j++)
    {
        if(lie[j]==o||abs(lie[j]-o)==abs(j-m))
        {
            return false;
        }
    }
    return true;
}
void dfs(int n)
{
    if(n==q+1)
    {
        sum++;
        return;
    }
    else
    {
        for(i=1;i<=q;i++)
        {
            if(pd(n,i))
            {
                lie[n]=i;
                dfs(n+1);
                i=lie[n];
            }
        }
    } 
}
int main()
{
    for(q=1;q<=10;q++)
    {
        sum=0;
        memset(lie,0,sizeof(lie));
        dfs(1);
        num[q]=sum;
    }
    while(1)
    {
        sum=0;
        scanf("%d",&t);
        if(t==0)
        {
            break;
        }
        printf("%d\n",num[t]);
    }
    return 0;
}

其中某些地方可以进行优化来缩减空间或者时间，但由于高中这么学的，所以在此就不作多少改动了。

洛谷 P1605 迷宫

一个简单的裸dfs问题，当然用bfs也能做。

题目

https://www.luogu.org/problem/P1605

思路

下面我随便给出一组数据(题目样例给的太简单了……)来作图进行解释。

作图如下

蓝色方块表示起点，红色方块表示终点，黑色方块表示障碍物。

像以前的dfs讲解一样，我们也做一个堆栈用来解释递归过程。

首先，我们将(1,1)也就是起始点入栈。然后在每个当前格子，对于四个方向的试探定一个先后顺序，我在这里规定先向右试探，然后按顺时针顺序旋转。

按照这个顺序，我们首先应该试探(1,1)的右侧格子即(1,2)即(1+0,1+1)发现该格子既没有在地图边界之外，也是一个可行的格子(不是墙)。若该格子为目标点，则方案数应当加一，并且回溯。但很明显这个格子只是一个普通的可行点，把该格子入栈。

接下来，对于当前格子即(1,2)的四个方向可行性进行试探，按照规定，我们首先试探(1,2)右侧的格子即(1,3)，发现可行，进行入栈操作。

而对于(1,3)这个点，首先仍然按照规定，试探该点右侧的格子，发现是墙，即不可行点。故按照我先前定的规则，试探该点下侧的格子即(2,3)，发现该点可行，故入栈。

由此由于该线路剩下所有点右侧均为墙，均不可行，故均向下试探，省略过程。

最后，(4,3)点入栈，对于该点的右侧，下侧，左侧三个方向的试探均失败。向上试探时，(3,3)点虽然可行，但是该点在之前的路线中已经存在，故仍然不可再次访问，这点要记住，不然可能会出现无限循环情况。

对于(4,3)点四个方向的试探均失败，故进行回溯操作，回溯到上一层，即栈顶为(3,3)。

而对于(3,3)这个点来说，向下的试探已经做完，按照规定，向左试探与向上试探均失败，故进行回溯操作，回溯到(2,3)。按此规则，最终回溯到初始状态，即只有(1,1)在栈内的状态。

对于初始点即(1,1)的向右试探已经完成，执行向下试探，发现(2,1)可行，故将(2,1)入栈。

由此规则，直到(6,1)入栈，向右试探才变得可行，故(6,2)入栈。

按照规则，走到一半将呈现如下线路图。

在当前点即(7,8)按逆时针试探，应试探(7,7)点，(7,7)点可行，入栈，但是对于(7,7)来说，四个方向均失败，故回溯，在(7,8)点时，只能向上试探，故形成如下线路图。

在(6,4)点时，对四个方向试探均失败，故回溯。同理，回溯到了(5,8)，在该点向上试探，(4,8)，(3,8)接连入栈，走入了目标点所在路线。

方案数加一，并且因为到达目标点，回溯到上一层，即(3,7)。由于(3,7)对于上边的试探失败，故再次回溯到(3,8)，此次向上试探可行，故走入(2,8)(1,8)(1,7)(1,6)这条路。

路已经走到头，很明显可以得到一直回溯到(8,2)的结论。故当前栈顶为(8,2)。对于(8,2)来说，向右试探已经结束，向下试探越界不可行，向左试探可行，到达(8,1)到达(7,1)却无路可走，又回溯到(8,2)。

又回溯到(7,2)，向左试探，(7,1)入栈，(8,1)入栈，(8,2)入栈，再次进行之前那轮右侧的操作，直到又找到一种方案。方案数加一，很明显再次回溯到(7,2)，这次仍需回溯到(6,2)(6,1)。

将此过程进行完毕后，得出最终的方案数。

代码

#include<stdio.h>
int xa[8]={1,0,0,-1};
int ya[8]={0,1,-1,0};
int a[10][10]={0};
int mak[10][10]={0};
int sum=0;
int n,m,t;
int sx,sy,fx,fy,tx,ty;
void dfs(int x,int y)	
{
    if(x==0||x==n+1||y==0||y==m+1)
    {
        return;
    }
    else if(a[x][y]==1||mak[x][y]==1)
    {
        return;
    }
    else if(x==fx&&y==fy)
    {
        sum++;
        return;
    }
    else	
    {
        mak[x][y]=1;
        for(int k=0;k<=3;k++)
        {
            dfs(x+xa[k],y+ya[k]);
        }
        mak[x][y]=0;
    }
}	
int main()
{
    int i;
    scanf("%d%d%d",&n,&m,&t);
    scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
    for(i=1;i<=t;i++)
    {
        scanf("%d%d",&tx,&ty);
        a[tx][ty]=1;
    }
    dfs(sx,sy);
    printf("%d",sum);
    return 0;
}

洛谷 P1706 全排列问题

比较经典的问题，没啥好解释的，特别注意的也就是输出格式。

题目

https://www.luogu.org/problem/P1706

思路

输出自然数1到n所有不重复的排列，用我们的思维方式，很容易看出可以用dfs来解。

我们在此将第k次选择的数字，作为第k层的数字。以输入样例即3为例：每层都有三个可选项(1,2,3)，但是条件是已经选过的数字不可以再次选中，我们便可以用数组记录是否已经选中。

第一次也即第一层选中1，第二层选中2，第三层选中3。而到了这时候，k即层数已经等于n，答案序列已经得到了一个，故将其输出。

然后进行回溯操作，回溯到第二层，第二层选中3，第三层选中2，得到第二个答案。

如此操作，得出并且按格式输出全部答案。

代码

#include<stdio.h>
int n;
int sum=0;
int v[15]; 
int b[15];
void dfs(int ceng)
{
    int k;
    for(int i=1;i<=n;i++)
    {
        if(v[i]==0)
        {
            sum++;
            b[sum]=i;
            v[i]=1;
            dfs(ceng+1);
            sum--;
            v[i]=0;
        }
    }
    if(ceng==n)
    {
        for(k=1;k<=n;k++)
        {
            printf("%5d",b[k]);
        }
        printf("\n");
        return;
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

洛谷 P1036 选数

题目

https://www.luogu.org/problem/P1036

思路

很明显，这道题是一道组合，按照我们正常的思维方式，自然能够想到dfs的解题思路。限界条件就是已选择的数字个数等于要求选择的数字个数。

以题目中所给数据为例，我们把第几个选择的数字当作第几层。如此，第一层我们首先选择第一个数字即3，然后第二层选择3之后的第一个数字即7，第三层选择12。已经选择了三个数字，进行判定，3+7+12=22，22不是一个素数，故总数不变。

判定结束后，第三层重新选择，选择当前数字即12的下一个数字19。进行判定，3+7+19=29是一个素数，故总数加一。这时第三层应该重新选择，但是19后面没有数字了，故第三层回溯到第二层，第二层进行重新选择，第二层选择了下一个数字即12，第三层选择19。3+12+19=38，38不是一个素数。

第三层无法重新选择，回溯第二层，第二层重新选择到了19，第三层又没数可选，故回溯到第二层，回溯到第一层，第一层选择下一个数字即7，第二层是12，第三层是19。7+12+19=34，不是一个素数。之后无情况出现，第一层无法选择，dfs结束。

代码

#include<stdio.h>
#include<math.h>
int n,k;
int a[25];
int sum=0,sum1=0;
int pd(int shu)
{
    int i;
    for(i=2;i<=sqrt(shu);i++)
    {
        if(shu%i==0)
        {
            return 0;
        }
    }
    return 1;
}
void dfs(int ceng,int ge)
{
    if(ceng==k)
    {
        sum+=a[ge];
        if(pd(sum)==1)
        {
            sum1++;
        }
        sum-=a[ge];
        return;
    }
    else
    {
        sum+=a[ge];
        for(int j=ge+1;j<=n;j++)
        {
            dfs(ceng+1,j);
        }
        sum-=a[ge];
    }
}
int main()
{
    int i;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        dfs(1,i);
    }
    printf("%d",sum1);
    return 0;
}

洛谷 AT1350 深さ優先探索

题目

https://www.luogu.org/problem/AT1350

思路

题目问高桥先生能否到达鱼店，很明显是一个地图类的搜索。地图类的搜索我也在上面的迷宫中讲过。这类题用dfs和bfs都可以，但是由于dfs代码编写简单，故我在此用dfs解题。

迷宫一题问有多少种方案，而这个题目问是否能够到达。这就是两个题目最大的区别，这个区别体现在已经回溯过的点是否有必要再次经过。对于这种是否连通的题目，已经回溯过的点确实可以再次经过，但该点衍生出的路径均已被证伪（若可以通向终点则已经跳出了搜索过程），所以再次对于该点的操作都是浪费时间。故我们可以记录每一个点是否已经经过。这种去掉无用操作的技巧叫做剪枝。

通过剪枝，我们可以大幅降低时间复杂度，在某些题目中，不剪枝会导致TLE（超时）。

代码

#include<stdio.h>
int jl=0;
char a[505][505];
int b[505][505]={0};
int n,m;
int xa[6]={1,-1,0,0};
int ya[6]={0,0,1,-1};
void dfs(int x,int y)
{
    if(a[x][y]=='g')
    {
        jl=1;
    }
    else if(x==0||x==n+1||y==-1||y==m||a[x][y]=='#')
    {
        return;
    }
    else
    {
        for(int k=0;k<=3;k++)
        {
            if(b[x+xa[k]][y+ya[k]]==0)
            {
                b[x+xa[k]][y+ya[k]]=1;
                dfs(x+xa[k],y+ya[k]);
            }
        }
    }
}
int main()
{
    int bei,bej;
    int i,j; 
    scanf("%d%d",&n,&m);
    char c=getchar();
    for(i=1;i<=n;i++)
    {
        gets(a[i]);
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=m-1;j++)
        {
            if(a[i][j]=='s')
            {
                bei=i;
                bej=j;
            }
        }
    }
    dfs(bei,bej);
    if(jl==1)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}

POJ 2386 Lake Counting

题目

http://poj.org/problem?id=2386

思路

这道题的表述大概为一个代表水的格子(W)，若周围八格也存在代表水的格子，则这些代表水的格子是同一个湖，最后要求得出湖的个数。

很明显的，该题是一道地图类搜索，bfs和dfs都可以做，但还是由于dfs编写简单，我选择用dfs解答。与一般的地图形dfs最显性的不同就是转移的方向由4个变成了8个。

我对题目所给的样例进行解释，题目给出的是10个字符串，首先需要对这些字符串进行处理，当然我把字符放进了二维数组（也可以把字符转化成数字放到二维整形数组中）。

总体的思路略有不同，因为询问整个地图中湖的个数，我们需要对整个地图进行穷竭搜索，对每一个点进行访问，判断是否是一个新的湖。有人可能会问，这不是没用dfs嘛……这里就出现了一个问题，新发现的这个W，是否与以前数过的W处于同一湖中，对于这个问题，我们进行如下操作。

对于新发现的一个W，对该位置进行dfs搜索（具体搜索的过程与上述地图类dfs相差无几）。穷竭搜索过程中，发现了（1，1）这个点的W，首先把该点的值赋成代表无水点的标志（这一步至关重要！！！），对于该点进行dfs搜索过程，我们从右侧开始逆时针进行试探，可以发现右侧直到下侧都没有W，到了右下的点即（2，2），发现了W，第二层变成了（2，2），与此同时，这个点也被赋值成点。dfs过程结束之后，处于地图左上角的这个湖已经被填成了平地，并且湖的总个数已经变成了1。至此，对于（1，1）这个点的穷竭搜索已经完成，向后面进行搜索。

下一个新出现的W在（1，10）这个点，按照上述方式填平右侧的湖，湖的总数目变成了2。

随后，前五行均为代表平地的标志了。穷竭搜索到了第六行，搜索到了（6，3）这个点，对该点进行dfs之后，左下角的湖已经填平，总数变成了3，整个地图已经全变成了平地，穷竭搜索仍然会一直搜索到最后一行的最后一个节点。

代码

#include<stdio.h>
char a[105][105];
int xa[8]={1,1,1,0,0,-1,-1,-1};
int ya[8]={1,0,-1,1,-1,1,0,-1};
int sum=0;
int n,m;
int i,j;
void dfs(int x,int y)
{
    if(x==0||x==n+1||y==0||y==m+1)
    {
        return;
    }
    else if(a[x][y]=='.')
    {
        return;
    }
    else
    {
        a[x][y]='.';
        for(int k=0;k<=7;k++)
        {
            dfs(x+xa[k],y+ya[k]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    char c=getchar();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%c",&a[i][j]);
        }
        c=getchar();
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j]=='W')
            {
                sum++;
                dfs(i,j);
            }
        }
    }
    printf("%d",sum);
    return 0;
}

洛谷 P1451 求细胞数量

题目

https://www.luogu.org/problem/P1451

思路

与上一道POJ的题目思路一样，不同的是这道题中数字1~9代表细胞。

没啥好说的……

代码

#include<stdio.h>
char a[105][105];
int xa[8]={1,0,0,-1};
int ya[8]={0,1,-1,0};
int sum=0;
int n,m;
int i,j;
void dfs(int x,int y)
{
    if(x==0||x==n+1||y==-1||y==m)
    {
        return;
    }
    else if(a[x][y]=='0')
    {
        return;
    }
    else
    {
        a[x][y]='0';
        for(int k=0;k<=3;k++)
        {
            dfs(x+xa[k],y+ya[k]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    char c=getchar();
    for(i=1;i<=n;i++)
    {
        scanf("%s",a[i]);
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=m-1;j++)
        {
            printf("%c",a[i][j]);
        }
    printf("\n");
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=m-1;j++)
        {
            if(a[i][j]!='0')
            {
                sum++;
                dfs(i,j);
            }
        }
    }
    printf("%d",sum);
    return 0;
}

POJ 1088 滑雪

题目

http://poj.org/problem?id=1088

思路

这道题也是一道地图类的搜索问题，但是与上述题都有不同的是这道题的数据范围，行数和列数最大值都为100，而对于每个点进行dfs相当于最大10^4次dfs，再细化计算的话基本可以确定会TLE。

但是自己模拟两遍的话就又会发现一些特征，如果这条路是递减的话，无论从哪里走到这里，这条路都是递减的，所以我就会有这样一个想法：是不是可以直接在那个位置直接记录由该位置所联通的最长路径。当由其他点经由dfs到达该点可以直接继承该点的最长路径数而不用多次进行重复操作，这也算另一种意义上的剪枝。

（貌似是叫做记忆化搜索？？？）

代码

#include<stdio.h>
int h[105][105],v[105][105];
int xa[8]={1,0,0,-1};
int ya[8]={0,1,-1,0};
int r,c;
int sum,max1,max;
void dfs(int x,int y)
{
    if(x==0||x==r+1||y==0||y==c+1)
    {
        return;
    }
    else if(v[x][y]!=1)
    {
        sum+=v[x][y];
        if(sum>max1)
        {
            max1=sum;
        }
        if(sum>max)
        {
            max=sum;
        }
        sum-=v[x][y];
        return;
    }
    else
    {
        sum+=1;
        if(sum>max)
        {
            max=sum;
        }
        if(sum>max1)
        {
            max1=sum;
        }
        for(int k=0;k<=3;k++)
        {
            if(h[x+xa[k]][y+ya[k]]<h[x][y])
            {
                dfs(x+xa[k],y+ya[k]);
            }
        }
        sum-=1;
    }
}
int main()
{
    int i,j;
    scanf("%d%d",&r,&c);
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            scanf("%d",&h[i][j]);
            v[i][j]=1;
        }
    }
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            dfs(i,j);
            v[i][j]=max1;
            max1=0;
        }
    }
    printf("%d",max);
    return 0;
}

洛谷 P1506 拯救oibh总部

题目

https://www.luogu.org/problem/P1506

思路

我们通过看样例和题目可以看出，一个不会被淹到的区域，外围一定是* 。我们可以对最外围的一圈进行dfs，然后把所有的0也就是洪水可以淹没的地方赋值成* ，然后对整个地图进行搜索，查找0的数量。

代码

#include<stdio.h>
int xa[5]={-1,0,1,0};
int ya[5]={0,-1,0,1};
char map[505][505];
int n,m;
int sum=0;
void dfs(int x,int y)
{
    for(int i=0;i<=3;i++)
    {
        if(x+xa[i]>=0&&x+xa[i]<=n&&y+ya[i]>=0&&y+ya[i]<=m)
        {
            if(map[x+xa[i]][y+ya[i]]=='0')
            {
                map[x+xa[i]][y+ya[i]]='*';
                dfs(x+xa[i],y+ya[i]);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n-1;i++)
    {
        scanf("%s",map[i]);
    }
    for(int t=0;t<=m;t++)
        {
        if(map[0][t]=='0')
        {
            dfs(0,t);
            map[0][t]='*';
        }	
        if(map[n-1][t]=='0')
        {
            dfs(n-1,t);
            map[n-1][t]='*';
        }
    }
    for(int t=0;t<=n;t++)
    {
        if(map[t][0]=='0')
        {
            dfs(t,0);
            map[t][0]='*';
        }
        if(map[t][m-1]=='0')
        {
            dfs(t,m-1);
            map[t][m-1]='*';
        }
    }
    for(int i=0;i<=n-1;i++)
    {
        for(int j=0;j<=m-1;j++)
            {
            if(map[i][j]=='0')
            {
                sum++;
            }
        }
    }
    printf("%d",sum);
    return 0;
}

未完待续……