搜索

发表于2021-09-13更新于2021-09-13阅读次数

dfs bfs …

DFS

模板1

需要标记相关信息时使用这种做法
且搜索到满足条件的会继续搜索，不会停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}

例题

题目链接 https://www.luogu.com.cn/problem/P1123
题意 一个N×M的由非负整数构成的数字矩阵，你需要在其中取出若干个数字， 使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻8个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。
对于100%的数据，N, M≤6,T≤20，T是样例数

  • 注意细节
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    /*** 
     * @Practice Win
     * 洛谷 P1123 取数游戏 
     * dfs 
     * 思路 简单dfs
     */
    #include<bits/stdc++.h>
    #pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
    using namespace std;
    #define Debug(x) cout<<#x<<':'<<x<<endl
    typedef long long ll;
    #define INF 0x7fffffff//10^9级别，不到2^32
    ll ar[11][11],vis[11][11],d[11][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1,0,0};
    //方向数组，便于对x周围的八个数操作，很巧妙！！！
    ll n,m,ans=0,maxx=0;
    void dfs(ll x,ll y){
        if(y==m+1){
            dfs(x+1,1);
            return ;
        }
        if(x==n+1){
            ans=max(ans,maxx);
            return ;
        }
        dfs(x,y+1);
        if(vis[x][y]==0){
            maxx+=ar[x][y];
            for(ll i=0;i<=8;i++){
                vis[x+d[i][0]][y+d[i][1]]++;//这里是++，不能是=1，因为一个数可能会被多次标记为不可访问
            }
            dfs(x,y+1);
            for(ll i=0;i<=8;i++){
                vis[x+d[i][0]][y+d[i][1]]--;
            }
            maxx-=ar[x][y];
        }
    }
    void init(){
        memset(vis,0,sizeof(vis));
        ans=maxx=0;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        ll t;
        cin>>t;
        while(t--){
            init();
            cin>>n>>m;
            for(ll i=1;i<=n;i++){
                for(ll j=1;j<=m;j++)  cin>>ar[i][j];
            }
            dfs(1,1);
            cout<<ans<<endl;
        }
        return 0;
    }


模板2

不需要标记相关结点信息时可以用这种写法
这种在搜索到第一个满足条件的结果就会停止搜索

1
2
3
4
5
6
7
bool dfs(ll step){
    if(step==n)  return true;//达到边界
    for(//遍历n个结点){
        if(dfs(step+1))  return ture;//满足则停止搜索
    }
    return false;
}

回溯法

其实我觉得更好理解的就是，如果当前条件已经不满足了，就不再往下继续找了，我觉得叫剪枝更合适吧。回溯？还要往回找？什么东东，搜索本身不久包括了回溯嘛，这名字取得确实误导人。