Depth first search (template use)

Depth-first search （ Templates use ）

Template source

• About the origin of the template , come from here

• This article only explains the use of the template through examples .

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=100;
bool vst[maxn][maxn]; //  Access tags 
int map[maxn][maxn]; //  Coordinate range 
int dir[4][2]={
    0,1,0,-1,1,0,-1,0}; //  The direction of the vector ,(x,y) Four directions around 

bool CheckEdge(int x,int y){
     //  Judgment of boundary conditions and constraints 
    if(!vst[x][y] && ...) //  Meet the conditions 
    return 1;
    else //  Conflict with constraints 
    return 0;
}

void dfs(int x,int y){
    
    vst[x][y]=1; //  Mark that the node has been accessed 
    if(map[x][y]==G){
     //  There's a target state G
        ...... //  Do something about it 
        return;
    }
    for(int i=0;i<4;i++){
    
        if(CheckEdge(x+dir[i][0],y+dir[i][1])) //  Generate the next rule according to 
            dfs(x+dir[i][0],y+dir[i][1]);
    }
    return; //  There is no lower level search node , to flash back 
}
int main(){
    
    ......
    return 0;
}

Example 1： Oil field

Title Description ：

An oil exploration company is exploring underground oil field resources according to diseases , Work in a rectangular area . They first divided the area into many small square areas , Then use exploration equipment to detect whether there is oil in each small square area . Areas containing oil are called oil fields . If two oil fields are adjacent （ At the level 、 Vertically or diagonally adjacent ）, Then they are part of the same reservoir . The reservoir may be very large and may contain many oil fields （ The number of oil fields does not exceed 100）. Your job is to determine how many different reservoirs are contained in this rectangular region .

Input ： The input file contains one or more rectangular regions . The second in each region 1 Each row has two positive integers m and n(1 \leq m,n \leq 100), Indicates the number of rows and columns in the region . If m = 0, Indicates the end of input ; Otherwise, there will be m That's ok , Every line has n Characters . Each character corresponds to a square area , character * Indicates no oil , character @ It means there is oil .

Output ： For each rectangular region , Each row outputs the number of reservoirs .

Algorithm design

• Use the depth first search algorithm

• The constraint condition is that the coordinates are out of bounds , Whether the corresponding point is an oil field , Tag array . common 3 individual

#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
int m,n;
char str[maxn][maxn];
bool vst[maxn][maxn]; //  Access tags 
int dir[8][2]={
    -1,-1,-1,0,-1,1,
                   0,-1,0,1,1,-1,
                   1,0,1,1};//  The direction of the vector ,(x,y) Four directions around 

bool check(int x,int y);
void dfs(int x,int y);
int main(){
    
    int count = 0;
    cin >> m >> n;
    memset(vst,false,sizeof(vst));
    for (int i = 0; i < m; ++i) {
    
        for (int j = 0; j < n; ++j) {
    
            cin >> str[i][j];
        }
    }
    for (int i = 0; i < m; ++i) {
    
        for (int j = 0; j < n; ++j) {
    
            if(!vst[i][j] && str[i][j] == '@'){
    
                dfs(i,j);
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}
bool check(int x,int y){
     //  Judgment of boundary conditions and constraints 
    if(!vst[x][y] && x >= 0 && x < m && y >= 0 && y < n && str[x][y] == '@'){
    
        return true;
    }
    else{
    
        return false;
    }
}

void dfs(int x,int y){
    
    vst[x][y]= true; //  Mark that the node has been accessed 
    for(int i=0;i<8;i++){
    
        if(check(x+dir[i][0],y+dir[i][1])) //  Generate the next rule according to 
            dfs(x+dir[i][0],y+dir[i][1]);
    }
    return; //  There is no lower level search node , to flash back 
}

Input ：

5 5
****@
*@@*@
*@**@
@@@*@
@@**@

Output ：

2

Training 3： Knight's journey

Title Description

The knight decided to travel around the world , Its movement mode is shown in the following figure . The world of knight is the chessboard of his life , The area of chessboard is larger than that of ordinary $8\times 8$ Small chessboard , But it is still rectangular . Can you help this knight make a travel plan ？ Find a way . The knight enters a square every time , You can start and end on any square of the chessboard .

Input ： Input the 1 The row contains a positive integer $T$, Represents the number of test cases . The... Of each test case 1 Each row contains two $m$ and $n(1\le m\times n\le 26)$, Express $m\times n$ The chessboard of , Line number identification ($1\sim m$), Identify columns with capital letters ($A\sim Z$).

Output ： The output of each test case contains “$Scenario #i: $” At the beginning of the line , among i It's from 1 Starting test case number . Then output the... In dictionary order in a single line 1 Paths , This path accesses all the squares of the chessboard . The name output path of the block should be accessed through the connection , The name of each square consists of a capital letter followed by a number . If there is no such path , You should output on one line “impossible”. There is a blank line between the test cases .

Algorithm design

• Pay attention to the output array path And end logo flag.

• Because the output is first and last , So when writing constraints , Put the chessboard Exchange of ranks

• The upper bound in the constraint is less than or equal to , Not less than , It can be equal .

• Mark the previous point as false.

#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
int m,n;
bool vst[maxn][maxn],flag; //  Access tags 
int path[30][2];
int dir[8][2]={
    -2,-1,-2,1,-1,-2,
               -1,2,1,-2,1,2,
               2,-1,2,1};//  The direction of the vector ,(x,y) Four directions around 
bool check(int x,int y); // constraint condition 
bool dfs(int x,int y,int step); // Depth-first search 
int main(){
    
    int T;
    cin>>T;
    for(int k=1;k<=T;k++)
    {
    
        memset(vst,false,sizeof(vst));
        cin>>m>>n;
        flag=false; // Whether the mark is found 
        cout<<"Scenario #"<<k<<":"<<endl;
        path[0][0]=1;// from (1,1) Begin your search , That's ok ：A
        path[0][1]=1;// Column 1
        vst[1][1]=true;// Mark has passed 
        if(dfs(1,1,1)){
     // The initial state （1,1）, They count ：1
            for(int i=0;i<m*n;i++)
                cout<<char(path[i][0]+'A'-1)<<path[i][1]; // The output path （ That's ok , Column ）
            cout<<endl<<endl;
        }
        else
            cout<<"impossible"<<endl<<endl;
    }
    return 0;
}
bool check(int x,int y){
     //  Judgment of boundary conditions and constraints 
    if(x >= 1 && x <= n && y >= 1 && y <= m && !vst[x][y] && !flag){
    
        return true;
    }
    return false;
}
bool dfs(int x,int y,int step){
    
    if(step==n*m) // The number of steps is equal to the total number of coordinate points on the chessboard , It means that , Can end 
        return flag = true; // Already found 
    for(int i=0;i<8;i++) //  Generate the next rule according to 
    {
    
        int x2=x+dir[i][0];
        int y2=y+dir[i][1];
        if(check(x2,y2)) // constraint condition 
        {
    
            vst[x2][y2]= true; // Mark the coordinates of walking 
            path[step][0]=x2; // Record line 
            path[step][1]=y2; // Record column 
            dfs(x2,y2,step+1); // Steps plus 1, Keep looking for 
            vst[x2][y2] = false; // If you can't get through, go back 
        }
    }
    return flag;
}

Training 4： Catch the cow

Title Description

John hopes to catch the escaped cow immediately . Currently John is at the node $N$, The cow is at the node $K(0\le N,K\le 100000)$ when , They are on the same line . John has two modes of transportation ： Walk and ride . If Niu doesn't know someone is chasing him , Stay where you are , So how long does it take John to catch the cow ？

• Walk ： John can go from any node in a minute $X$ Move to node $X-1$ or $X+1$.
• By bus ： John can go from any node in a minute X Move to node $2\times X$.

Input ： Two integers $N$ and $K$.

Output ： The shortest time required for John to catch the cow （ In minutes ）.

Algorithm design

• The way of deep search is different from other topics , The way of moving has changed , And there is a certain regularity .

#include<iostream>
using namespace std;
int n,s;
int dfs(int t); // from n At position t The minimum number of steps （ Deep search ）
int main(){
    
    scanf("%d %d",&n,&s);
    if(n == 0){
     // If n = 0 Then go one step first to 1, Otherwise, you can't take the bus 
        n++;
        printf("%d",dfs(s)+1);
    }
    printf("%d",dfs(s));
    return 0;
}
int dfs(int t){
    
    if(t <= n){
     // Don't ride backwards , So we can only go backwards step by step 
        return n - t;
    }
    if(t % 2 == 1){
     // If t It's odd , Compare from t-1 forward 1 Step to t、 from t+1 backward 1 Step to t Which one has less steps 
        return min(dfs(t+1)+1,dfs(t-1)+1);
    }
    else{
     // If t For the even , Compare from t/2 Take a bus to t、 from n What kind of steps are few step by step 
        return min(dfs(t/2)+1,t-n);
    }
}

Input ：

5 17

Output ：

4