Search element topic （DFS ）

Preface

  Searching is a violent method 
  It can be understood according to the tree 
  Without cutting the branch , Can put all  * programme * “ enumeration ” come out 
  Scissor branch  -->  When it is certain that it will not be the solution , Early termination of the " spot " The following search elements 

Similar to tree structure

---

A problem can be divided into several sub parts to solve （ somewhat DP It smells good. , But this lesson is just a simple search , Direction consumption ）

In other words ：

If the problem is abstracted into a set , Each element can be regarded as a local scheme

all A subset of elements May be a solution to the problem

If you feel a little dizzy

Let's have a practical question to help the fun

123 These three numbers are all arranged

Every set on the graph , Is a solution to the problem

Such as ：3 1 2

---

Full Permutation implementation code

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
bool st[N];
int ans[N];
int n;
void dfs(int cnt)
{
    
    if (cnt == n)
    {
    
        for (int i = 1; i <= n; i++)
        {
    
            cout << ans[i];
            cout << (i == n ? '\n' : ' ');
        }
    }
    for (int i = 1; i <= n; i++)
    {
    
        if (!st[i])
        {
    
            ans[cnt + 1] = i;
            st[i] = 1;
            dfs(cnt + 1);
            st[i] = 0;
        }
    }
}
void solve()
{
    
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
    
        ans[1] = i;
        st[i] = 1;
        dfs(1);
        st[i] = 0;
    }
}
int main()
{
    
    solve();
}

Templates

void dfs( Parameters to be used )
{
    
    if( Meet the conditions of the topic )
    {
    
        xxx
    }

    if( The boundary conditions  |  Scissor branch )
    {
    
        xxx
        return 
    }

     agile dfs The process 
     Write according to the meaning of the title , Very flexible ！
     How can I feel comfortable  (:

    for ( Conditions )
    {
    
        xxx
        xxx
        st[idx] = 1;//****
        dfs(xxx)
        st[idx] = 0//****
    }
    
    or

    dfs(xxx)

     wait 

    cout << ans << '\n';
}

subject

P2392 kkksc03 Cramming before the exam

https://www.luogu.com.cn/problem/P2392

AC Code

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;

int a[N];
int n1, n2, n3, n4;
int ans = 0, tt = 0;
int nn;
void dfs(int l, int r, int cnt)
{
    
    if (cnt == nn)
    {
    
        tt = min(tt,max(l, r));
        return;
    }
        dfs(l + a[cnt + 1], r, cnt + 1);
        dfs(l, r + a[cnt + 1], cnt + 1);
}
void solve()
{
    
    cin >> n1 >> n2 >> n3 >> n4;

    for (int i = 1; i <= n1; i++)
        cin >> a[i];
    nn = n1, tt = 0x3f3f3f3f;
    dfs(0, 0, 0);
    ans += tt;

    for (int i = 1; i <= n2; i++)
        cin >> a[i];
    nn = n2, tt = 0x3f3f3f3f;
    dfs(0, 0, 0);
    ans += tt;


    for (int i = 1; i <= n3; i++)
        cin >> a[i];
    nn = n3, tt = 0x3f3f3f3f;
    dfs(0, 0, 0);
    ans += tt;

    for (int i = 1; i <= n4; i++)
        cin >> a[i];
    nn = n4, tt = 0x3f3f3f3f;
    dfs(0, 0, 0);
    ans += tt;

    cout << ans << endl;
}
int main()
{
    
    solve();
}

P1135 Strange elevator

https://www.luogu.com.cn/problem/P1135

T Code

---

Too violent , Failed to deal with repeated local schemes

In other words ： Cutting and supporting treatment is not in place

---

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int s[N];
int n, bg, ed;
int ans = 0x3f3f3f3f;

void dfs(int idx, int cnt)
{
    
    if (idx <= 0 || cnt > n)
        return ;
    if (idx == ed)
    {
    
        ans = min(ans, cnt);
        return ;
    }
    dfs(idx + s[idx],cnt + 1);
    dfs(idx - s[idx],cnt + 1);
}

void solve()
{
    
    cin >> n >> bg >> ed;

    for (int i = 1; i <= n; i++)
        cin >> s[i];

    dfs(bg,0);

    cout << (ans == 0x3f3f3f3f ? -1 : ans) << '\n';
}
int main()
{
    
    solve();
}

AC Code

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int s[N];
int n, bg, ed;
int ans = 0x3f3f3f3f;
bool st[N];
void dfs(int idx, int cnt)
{
    
    if (idx <= 0 || cnt > n || st[idx] || idx > n || cnt >= ans)
        return ;
    if (idx == ed)
    {
    
        ans = min(ans, cnt);
        return ;
    }
    st[idx] = 1;
    dfs(idx + s[idx],cnt + 1);
    dfs(idx - s[idx],cnt + 1);
    st[idx] = 0;
}

void solve()
{
    
    cin >> n >> bg >> ed;

    for (int i = 1; i <= n; i++)
        cin >> s[i];

    dfs(bg,0);

    cout << (ans == 0x3f3f3f3f ? -1 : ans) << '\n';
}
int main()
{
    
    solve();
}

This topic の summary

1. Correct use of marks 
2. Judgment of shear branch  &  Optimize 
...

Count class

P1605 maze

https://www.luogu.com.cn/problem/P1605

AC Code

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int n, m, t;
int bgx, bgy, edx, edy;
int s[N][N];
bool st[N][N];
int xx[4] = {
    0, 1, -1, 0}, yy[4] = {
    1, 0, 0, -1};
int ans;
void dfs(int x, int y)
{
    
    if (x == edx && y == edy)
    {
    
        ans++;
        return;
    }

    for (int i = 0; i < 4; i++)
    {
    
        int tx = x + xx[i], ty = y + yy[i];

        if ((tx >= 1 && tx <= n) && (ty >= 1 && ty <= m) && !s[tx][ty] && !st[tx][ty])
        {
    
            st[x][y] = 1;
            dfs(tx, ty);
            st[x][y] = 0;
        }
    }
}
void solve()
{
    
    cin >> n >> m >> t;

    cin >> bgx >> bgy >> edx >> edy;
    for (int i = 1; i <= t; i++)
    {
    
        int a, b;
        cin >> a >> b;
        s[a][b] = 1;
    }
    dfs(bgx, bgy);

    cout << ans << endl;
}
int main()
{
    
    solve();
}