【算法】DFS 刷题总结

一.一道好题！[SCOI2005]栅栏（贪心+二分+dfs）

P2329 [SCOI2005]栅栏
题目描述
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。
你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。
输入格式
第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。
接下来一行(即第m+2行)为整数n(n <= 1000)，表示约翰需要多少木材。
接下来n行表示他所需要的每一块木板的长度。木材的规格小于32767。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。
输出格式
只有一行，为约翰最多能够得到的符合条件的木板的个数。

输入：
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30
输出：
7

这是一个链接，是答案啦

二.记忆化搜索

边界条件与递归方程是递归函数的两个要素。

递归构建有三个条件：
1）参数；
2）边界；
3）范围。
据此来分析递归过程如何写。
1）参数：明确参数的意义以及当前的值；
2）边界：一个递归函数一定要有边界，而且边界一定要考虑全面，不能漏，否则它就可能死循环；
3）范围：就是你在递归时的选择往哪儿走，也就是说，你的递归调用的函数返回值。
然后我们现在再来看一下记忆化搜索：
①定义好一个数组，用来存储递归所求出来的值；②在主程序里，memset一下，一般都是赋初值为-1，然后把这个数组的边界值设置好；③在递归函数里，首先加一句：if （这个数组的值>=0） return 这个值【如果赋初值为-1的话，一般都是>=0】；其次，在后面的递归调用中，先给这个数组赋值，再return。（这一段话转自CSDN）

例题：P1434 [SHOI2002]滑雪
题目描述
Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1   2   3   4   5
16  17  18  19   6
15  24  25  20   7
14  23  22  21   8
13  12  11  10   9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可行的滑坡为24－17－16－1（从24开始，在1结束）。当然25－24－23－…－3－2－1更长。事实上，这是最长的一条。
这里是答案的链接哦

三. 深搜染色

例题1：单词方阵
给一n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 888 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：

输入：
    8                     输出：
    qyizhong              *yizhong
    gydthkjy              gy******
    nwidghji              n*i*****
    orbzsfgz              o**z****
    hhgrhwth              h***h***
    zzzzzozo              z****o**
    iwdfrgng              i*****n*
    yyyygggg              y******g

很典型的深搜题，向八个方向搜索，找到y后找i，然后保存方向，朝着这个方向去搜，单词全部搜到符合题意就用vis数组标记路径,未被标记的输出*即可。
注意
1.最好定义一个结构体数组来保存路径（x,y）；
2.函数别忘了写return不然会re关键是codeblocks上能编译通过…；
3.按题目要求用s[];保存单词；
4.s[]是从0开始的所以step==6的时候单词搜索完毕继续+1再调用一次用于保存路径（这样才能路径完整）。

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[105][105];
char mp[105][105],s[]="yizhong";
struct node
{
    int x,y;
}way[105];
int dir[][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
void dfs(int sx,int sy,int di,int step)
{
    if(step==7)
        for(int i=0;i<7;i++)
        vis[way[i].x][way[i].y]=1;
    else {
        int nx=sx+dir[di][0];
        int ny=sy+dir[di][1];
        if(mp[nx][ny]==s[step+1]||step==6)
        {
            way[step].x=sx;
            way[step].y=sy;
            dfs(nx,ny,di,step+1);
        }
    }

}
int main()
{
    cin>>n;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        cin>>mp[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(mp[i][j]=='y')
            {
                for(int k=0;k<8;k++)
                {
                    int x=i+dir[k][0];
                    int y=j+dir[k][1];
                    if(mp[x][y]=='i')
                        dfs(i,j,k,0);
                }

            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(vis[i][j]==1)
            cout<<mp[i][j];
            else cout<<'*';
            if(j==n)cout<<endl;
        }
    return 0;
}

四.UVA1103 古代象形符号 Ancient Messages（DFS，字符串）

题目翻译
为了识别3000年前古埃及用到的6种象形文字。每组数据包含一个H行W列的字符矩阵（H≤200，W≤50 ），每个字符为4个相邻像素点的十六进制（例如，10011100对应的字符就是9c）。转化为二进制后1表示黑点，0表示白点。输入满足以下条件：

不会出现上述6种符号之外的其他符号。
输入至少包含一个符号，且每个黑像素都属于一个符号。输入至少包含一个符号，且每个黑像素都属于一个符号。
每个符号都是一个四连块，并且不同符号不会相互接触，也不会相互包含。
如果两个黑像素有公共顶点，则它们一定有一个相同的相邻黑像素（有公共边）。
符号的形状一定和题中的图形拓扑等价（可以随意拉伸但不能拉断）。

要求按照字典序输出出现的所有符号。

输出说明：
For each test case, display its case number followed by a string containing one character for each
hieroglyph recognized in the image, using the following code:
Ankh: A
Wedjat: J
Djed: D
Scarab: S
Was: W
Akhet: K

Sample Input

100 25
0000000000000000000000000
0000000000000000000000000
...(50 lines omitted)...
00001fe0000000000007c0000
00003fe0000000000007c0000
...(44 lines omitted)...
0000000000000000000000000
0000000000000000000000000
150 38
00000000000000000000000000000000000000
00000000000000000000000000000000000000
...(75 lines omitted)...
0000000003fffffffffffffffff00000000000
0000000003fffffffffffffffff00000000000
...(69 lines omitted)...
00000000000000000000000000000000000000
00000000000000000000000000000000000000
0 0