·Search - Depth First Search Chapter 1 [Full Arrangement]

1. Depth-first search, also known as dfs

Deep search, as the name suggests, is a search algorithm based on depth, which is essentially a recursive

It's just a more luxurious recursion

Deep search background and basic knowledge points

Abbreviation of deep search	use background	reference model	question type
dfs	find all solutions; full permutation; find the number of methods used; graph theory;	stack and recursion	Full arrangement; two-dimensional deep search;

TIPS: dfs generally starts searching from 1. Unlike the commonly used recursion, some deep searches do not need to call themselves, such as the following question:

Luogu Portal: P1706 Full alignment problem

Password Island OJ Portal: #1244. Full permutation

full permutation problem

topic description

Output all non-repeating permutations of natural numbers 1 to n in lexicographical order, that is, the full permutation of n. It is required that repeated numbers are not allowed in any sequence of numbers generated.

input format

an integer n.

output format

All non-repeating sequences of numbers from 1∼n, one sequence per line.

5 field widths are reserved for each figure.

Sample #1

Sample input #1

3

Sample output #1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

hint

1≤n≤9.

The original intention of this question is to find the arrangement, similar to the A in the permutation combination, each number must be arranged more than once.

Randomly select m (m≤n) elements from n different elements and arrange them in a certain order, which is called an arrangement of taking m elements from n different elements. When m=n, all permutations are called full permutations. --Baidu Encyclopedia

So through the meaning of the title, we can know that the exit of the number of full permutations is that when m=n, it ends

When we see the problem, the first reaction must be to use a loop. For example, this Konjac thought at the beginning:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cout<<i;
    } 
    return 0;
}

But the situation is not quite right.

What people want is the full arrangement! ! All lined up! ! You just output the number! !

It doesn't matter, things have to start from the root. Let's see what happens if we want to output two numbers at once.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<i<<" "<<j;
        } 
    } 
    return 0;
}

A very Wonderful enumeration with no technical content.

What if you want to output three numbers at a time? ?

#include<bits/stdc++.h>
using namespace std;
 int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                cout<<i<<" "<<j<<" "<<k;
            } 
        } 
    } 
    return 0;
}
//watermark

A very untechnical enumeration. At this point you are already in danger of TLE.

At this time, it makes no sense to you to think that if you continue to enumerate like this, you don't know how many cycles you need to write.

So you want to use a function, but you don't know how many times the function will be called.

At this time deep search it appeared

But how to write deep search, the first step you still only know to use loops. Then write a loop 8

for(int i=1;i<=n;i++){
        printf("%5d",a[i]);
    }
    cout<<endl;
}

Very Wonderful. Cordoli gives you thumbs up.

But you still have to control the scope, so write another if:

if(x>n){
    for(int i=1;i<=n;i++){
        printf("%5d",a[i]);
    }
    cout<<endl;
}

But you are only satisfied with the output, and you have to judge what to do if the output cannot be output, so we can use the else statement:

else{ }

But what to write in else? ? Back to the original topic of Deep Search

What does the title want you to do? To output the full arrangement of 1-n If it is guaranteed not to be repeated, then you also need a marker to mark whether it has been repeated.

With what mark? Use a single variable? It must not work. People have a bunch of numbers for you to arrange, then create an array of 8

bool b[1000]={0};

Same old, a for loop. First judge whether it has been used, that is, judge whether b[i]==1. If it is, it means it has been used, just continue and prune. Don't forget to mark it as 1 after traversing.

else{
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            continue;
        }
        b[i]=1;
    }
}

What about after tagging? After you search deeply, it means that your numbers have been sorted out in this operation, and you have to start picking three numbers again. Then you have to change the original marked 1 to 0 at this time.

else{
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            continue;
        }
        b[i]=1;
        b[i]=0;
    }
}

Since you are going to do a deep search, then look back at what you output when you output the above. You output a[i]. Then you must store your value in the a[ ] array. Since x is decremented at each level, it represents the number of searches, so you can use x as the subscript of a , and then save i.

The complete code of the deep search part is as follows:

int n;
int a[100];
bool b[1000]; 
void dfs(int x){
    if(x>n){
        for(int i=1;i<=n;i++){
            printf("%5d",a[i]);
        }
        cout<<endl;
    }else{
        for(int i=1;i<=n;i++){
            if(b[i]==1){
                continue;
            }
            b[i]=1;
            a[x]=i;
            dfs(x+1);
            b[i]=0;
        }
    }
} 

But you still need the main function. main starts searching from 1, so the complete code of the whole question with the main function is as follows:

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<climits>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
int n;
int a[100];
bool b[1000]; 
void dfs(int x){
    if(x>n){
        for(int i=1;i<=n;i++){
            printf("%5d",a[i]);
        }
        cout<<endl;
    }else{
        for(int i=1;i<=n;i++){
            if(b[i]==1){
                continue;
            }
            b[i]=1;
            a[x]=i;
            dfs(x+1);
            b[i]=0;
        }
    }
} 
int main(){
    cin>>n;
    dfs(1);
    return 0;
}

Perfect, AC sprinkled flowers, this question is perfect.

Today is a full-arrangement article, I don’t want to write it anymore, it’s too long, I’ll talk about expansion 8 next time

888888888888886