Depth first search - DFS (burst search)

DFS Application of ideas - Solve the problem exhaustively

When there is no way to go , We often choose search algorithm , Because we expect to use the high performance of computers to purposefully enumerate some or even all possible situations of a problem , So as to find the answer that meets the requirements of the question in these situations . This is also “ Explosive search ” In the name of   origin

We have an agreement , For the intervention status of the problem , It's called The initial state , The required state is Target state .
The search here is right Real time generated state Conduct analysis and detection , Until you get one The target state or the best state that meets the requirements until . The process of generating new states in real time is called Expand （ By a state , Application rules , The process of producing a new state ）

Key points of search ：

1. Select the initial state , In some problems, you may search from multiple legal states ;

2. Traverse the legal state generated from the initial state or current state , Generate a new state and enter recursion ;

3. Check whether the new state is the target state , Yes, go back to , Otherwise, continue to traverse , repeat 2-3 step

Processing of state ：DFS when , Use an array to store all the generated States

1. Put the initial state into the array , Set to current state ;
2. Expand the current state , Find a new state from the middle of the legal state and put it into the array , At the same time, set the newly generated state as the current state ;
3. Judge whether the current state is the same as the previous state , If repeated, return to the previous state , Another state that produces it ;
4. Judge whether the current state is the target state , If it is the target target state , Find a solution , According to the actual problem demand , Choose to continue looking for answers or go back directly .
5. If the array is empty , It shows that there is no solution to this problem .

 

Catalog

842. Arrange numbers

843. n- queens problem

P1036 [NOIP2002 Popularization group ] Selection

topic 1 And questions 3 Combined practice ：

        P1157 Combined output

---

842. Arrange numbers

Given an integer  n, The digital  1∼n  In a row , There will be many ways to arrange .

Now? , Please output all the arrangement methods in dictionary order .

Input format

All in one line , Contains an integer  n.

Output format

Output all permutation schemes in dictionary order , One line for each scheme .

Data range

1≤n≤7

sample input ：

3

sample output ：

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

  First draw a recursive search tree

Ideas ： 

• use path Array save arrangement , When the length of the arrangement is n when , It's a scheme , Output .
• use st  The array indicates whether the number has been used . When st[i] by 1 when ：i Has been used ,st[i] by 0 when ,i Not used .
• dfs(i) It means ： stay path[i] Fill in the number in the box , Then recursively fill in the number in the next position .
• to flash back ： The first i After all the cases of filling in a number in a position are traversed , The first i Fill in the next number in one place .

#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N];
bool st[N];

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++) cout<<path[i]<<" ";
        puts("");
        return ;
    }
    for(int i=1;i<=n;i++)
        if(!st[i])
        {
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

843. n- queens problem

n− The Queen's problem means that  n  Put a queen in  n×n  On my chess board , So that the queen can't attack each other , That is, no two Queens can be in the same line 、 On the same column or slash .

Now, given an integer  n, Please output all the pieces that meet the conditions .

Input format

All in one line , Contains integers n.

Output format

Each solution accounts for  n  That's ok , Each line outputs a length of  n  String , Used to represent the complete chessboard state .

among  .  Indicates that the grid status of a position is empty ,Q  The queen is placed on the square indicating a certain position .

After the output of each scheme is completed , Output a blank line .

Be careful ： There must be no extra spaces at the end of the line .

The order of output schemes is arbitrary , As long as there is no repetition and no omission .

Data range

1≤n≤9

sample input ：

4

sample output ：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

Method 1、（DFS Press the line enumeration ） Time complexity O(n*n!)

The code analysis

Diagonals dg[u+i], Anti diagonal udg[n−u+i] Subscript in u+i and n−u+i It means intercept

In the following analysis (x,y) Equivalent to (u,i)
Anti diagonal y=x+b intercept b=y−x, Because we're going to b As an array subscript , obviously b Can't be negative , So we add +n （ actually +n+4,+2n Will do ）, To ensure that the result is positive , namely y - x + n
And diagonals y=−x+b, The intercept is b=y+x, The intercept here must be positive , So you don't need to add an offset

Core purpose ： Find some legal subscripts to indicate dg or udg Whether it has been marked , So if you want to , You take udg[n+n−u+i] It's fine too , As long as all (u,i) Yes, it can be mapped to the past

summary ： Because the slope of the slash is the same , So the only difference is intercept , The same intercept is the same slash
 

#include <iostream>
using namespace std;
const int N = 20; 

// bool Array is used to determine whether the next location of the search is feasible 
// col Column ,dg Diagonals ,udg Anti diagonal 
// g[N][N] Used to save path 

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
    // u == n  It means that we have searched n That's ok , So output this path 
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(g[i]);   //  Equivalent to cout << g[i] << endl;
        puts("");  //  Line break 
        return;
    }

    // Yes n Search by line from one location 
    for (int i = 0; i < n; i ++ )
        //  prune ( For points that do not meet the requirements , No more searching )  
        // udg[n - u + i],+n To ensure that the subscript is nonnegative 
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false; //  Restore the scene   This step is crucial 
            g[u][i] = '.';

        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}   

Method 2、（DFS Press Every element enumeration ） Time complexity O(2^(n^2))

#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; //  Because it's a search , So I added row

// s Indicates the number of queens that have been put on 
void dfs(int x, int y, int s)
{
    //  Because from 0 Start ,y==n Time out of bounds , Deal with situations beyond the boundary 
    if (y == n) y = 0, x ++ ;

    if (x == n) { // x==n Description has been enumerated n^2 It's a place 
        if (s == n) { // s==n It means that it was successfully put on n A queen 
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    //  Branch 1： Put the queen 
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }

    //  Branch 2： Don't let the queen go 
    dfs(x, y + 1, s);
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}

P1036 [NOIP2002 Popularization group ] Selection

know n It's an integer x1,x2,…,xn, as well as 11 It's an integer k (k < n). from n Any number of integers k Add the whole numbers , We can get a series of and respectively . For example, when n = 4,k = 3 , 4 The integers are 3,7,12,1 when , All the combinations and their sum can be obtained as ：

3+7+12=2

3+7+19=2

7+12+19=3

3+12+19=3

Now? , Ask you to work out how many kinds of sum are prime numbers .

For example, the above example , There is only one sum of prime numbers ：3+7+19=2.

Input format

Keyboard entry , The format is ：

n , k (1 <= n <= 20 , k < n)
x1,x2,…,xn(1 <= xi <= 5000000)

Output format

Screen output , The format is ： 1 It's an integer （ The number of species that satisfy the condition ）.

I/o sample

Input

4 3
3 7 12 19

Output

1

Ideas  

Principle of no decline
Because it is to find the number of species , So we need to get rid of it , A little bit of a problem , So it is arranged in the order from small to large

for example , stay 1 2 3 4, Choose three of the four numbers
1 2 3
1 2 4
1 3 4
because 123 Follow 213,231,312… Although the order is different , But noumenon is summation , Their sum is equal , Is the result of repetition

therefore , From large to small output , Avoid repetition

Concrete realization , Look at the following code ,dfs The parameters of the function ks, It means that the position of the currently selected number in all numbers is ks individual ,
for The cycle also starts from ks Start , It saves cycle time , And avoid repetition
after dfs recursive i+1, Automatically select a larger number to sort
 

#include<iostream>
#include<cmath>
using namespace std;
const int N=21;

int n,sum,k,tot;
int a[N];

int zs(int n)
{
	if(n<2) return 0;
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0) return 0;
	return 1;
}

void dfs(int m,int sum,int ks)// Start coordinates to prevent repetition 
							  // If present 1+2+3 and 1+3+2 
{
	if(m==k)
	{
		if(zs(sum))
		{
			tot++;
		}
		return ;
	}
	
	for(int i=ks;i<n;i++)
	{
		dfs(m+1,sum+a[i],i+1);	//i+1, Just add in ascending order to prevent repetition  
	}
	return ;
}

int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	dfs(0,0,0);	// The layer number , Add and , Start coordinates  
	cout<<tot;
	return 0;
}

topic 1 And questions 3 Combined practice ：

P1157 Combined output

Input #1

5 3 

Output #1

  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

Ideas ： Painting trees + Principle of no decline

#include<bits/stdc++.h>
using namespace std;

int n,k;
int a[22];
bool st[22];
void dfs(int m,int ks)
{
	if(m==k)
	{
		for(int i=0;i<k;i++)
		{
			printf("%3d",a[i]);
		}
		puts("");
	}
	
	for(int i=ks;i<=n;i++)
	{
		if(!st[i])
		{
			a[m]=i;
			st[i]=true;
			dfs(m+1,i+1);
			st[i]=false;
		}
	}
}

int main()
{
	cin>>n>>k;
	dfs(0,1);
	return 0;
} 

I feel that search is finally getting started ......