Breadth first search (template use)

Breadth 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<queue>
#include<algorithm>
using namespace std;
const int maxn=100;
bool vst[maxn][maxn]; //  Access tags 
int dir[4][2]={
    0,1,0,-1,1,0,-1,0}; //  The direction of the vector 

struct State{
     // BFS  Status data structure in the queue 
    int x,y; //  coordinates 
    int Step_Counter; //  Search step counter 
};

State a[maxn];

bool CheckState(State s){
     //  Constraint test 
    if(!vst[s.x][s.y] && ...) //  Meet the conditions 
    return 1;
    else //  Constraint conflict 
    return 0;
}

void bfs(State st){
    
    queue <State> q; // BFS  queue 
    State now,next; //  Definition 2  Status , Current and next 
    st.Step_Counter=0; //  Counter reset 
    q.push(st); //  The team 
    vst[st.x][st.y]=1; //  Access tags 
    while(!q.empty()){
    
        now=q.front(); //  Take the first element of the team to expand 
        if(now==G){
     // There's a target state , This is the case Step_Counter  The minimum value of , You can quit 
            ...... //  Do the relevant processing 
            return;
        }
        for(int i=0;i<4;i++){
     //  If the status meets the constraints, join the team 
            next.x=now.x+dir[i][0]; //  Generate the next status according to the rules 
            next.y=now.y+dir[i][1];
            next.Step_Counter=now.Step_Counter+1; //  Counter plus 1
            if(CheckState(next)){
    
                q.push(next);
                vst[next.x][next.y]=1; // Access tags 
            }
        }
        q.pop(); //  The first element out of the team 
    }
    return;
}

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\le m,n\le 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 breadth first search template to solve

• 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 = 10;
int m,n; // Row number , Number of columns 
int ans = 0; // Number of oil fields 
bool vst[maxn][maxn]; //  Access tags 
char str[maxn][maxn]; // Oilfield matrix 
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 
struct state{
     // BFS  Status data structure in the queue 
    int x,y; //  coordinates 
    int step; //  Search step counter 
};
bool check(state s); // Constraint test 
void bfs(int i,int j); // Breadth first search 
int main(){
    
    memset(vst,false,sizeof(vst)); // Tag array initialization 
    cin >> m >> n;
    for (int i = 0; i < m; ++i) {
     // Storage oil field 
        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(str[i][j] == '@' && !vst[i][j]){
    
                bfs(i,j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
bool check(state s){
      //  Constraint test 
    if(s.x >= 0 && s.x < m && s.y >= 0 && s.y < n && str[s.x][s.y] == '@' && !vst[s.x][s.y]){
    
        return true;
    }
    return false;
}

void bfs(int i,int j){
    
    queue<state> q; //BFS queue 
    state now,next; // Definition 2 Status , Current and next 
    next.x = i; // Join the oil field 
    next.y = j;
    next.step = 0;
    q.push(next);
    vst[next.x][next.y] = true;
    while(!q.empty()){
    
        now = q.front(); // Take the first element of the queue to expand 
        for (int k = 0; k < 8; ++k) {
     //8 Expand in two directions 
            next.x = now.x+dir[k][0]; // Generate the next status according to the rules 
            next.y = now.y+dir[k][1];
            next.step = now.step+1;
            if(check(next)){
     // Determine whether the constraints are met 
                q.push(next);
                vst[next.x][next.y] = true; // Tag access 
            }
        }
        q.pop(); // The first element out of the team 
    }
}

Input ：

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

Output ：

2

Example 2： 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

• This problem is in one-dimensional space , It is slightly different from two-dimensional space .

• The way of moving has changed , This can be seen in the update status .

• The constraint is , One dimensional coordinate is greater than 0 And less than 50（ there 50 Mainly to prevent meaningless search , Because once you exceed 50, Even if you go back, it must not be the optimal solution , So it depends on the position of the cow ）, Tag array , common 3 individual

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
int n,k;// John's distance 、 Distance of cattle 
bool vst[maxn]; //  Access tags 
struct state{
     // BFS  Status data structure in the queue 
    int x; //  coordinates 
    int time; //  Search takes time 
};
bool check(state s); // Constraint function 
void bfs(int temp); // Breadth first search 
int main(){
    
    cin >> n >> k;
    memset(vst,false,sizeof(vst)); // Tag array initialization 
    bfs(n); // Starting from 5, from 5 Start breadth first search 
}
bool check(state s){
      //  Constraint test 
    if(s.x >= 0 && s.x <= 50 && !vst[s.x]){
    
        return true;
    }
    return false;
}

void bfs(int temp){
    
    queue<state> q;
    state now,next; //  Definition 2  Status , Current and next 
    next.x = temp;
    next.time = 0;
    q.push(next);
    vst[temp] = true; // Tag access 
    while(!q.empty()){
    
        now = q.front();
        if(now.x == k){
     // There's a target state , Output time , Exit can 
            cout << now.time << endl;
            return;
        }
        next.x = now.x+1; // Generate the next status according to the rules 
        if(check(next)){
    
            next.time = now.time + 1; // Time to update the next status 
            vst[next.x] = true; // Access tags 
            q.push(next); // The team 
        }
        next.x = now.x-1; // Generate the next status according to the rules 
        if(check(next)){
    
            next.time = now.time + 1; // Time to update the next status 
            vst[next.x] = true; // Access tags 
            q.push(next); // The team 
        }
        next.x = now.x*2; // Generate the next status according to the rules 
        if(check(next)){
    
            next.time = now.time + 1; // Time to update the next status 
            vst[next.x] = true; // Access tags 
            q.push(next); // The team 
        }
        q.pop(); // Out of the team 
    }
}

Input ：

5 17

Output ：

4

test questions C： Spread

Problem description

Xiaolan paints on an infinite special canvas .
This canvas can be seen as a grid , Each lattice can be represented by a two-dimensional integer coordinate .
Xiao Lan first made a few dots on the canvas （0,0）、（2020,11）、（11,14）、（2000,2000）. Only these squares have black , Other positions are white .
Every minute , The black will spread a little bit . Concrete , If a grid is full of black , It's going to spread to 、 Next 、 Left 、 In the right four adjacent squares , Make these four squares black （ If it turns out to be black , It's still black ）.
Excuse me, , after 2020 Minutes later , How many squares on the canvas are black .

Algorithm design

• Violent solution is easy to explode memory , So choose BFS（ Breadth first search ） Algorithm is a method .

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int ans = 4; // Already exist 4 A black spot 
bool vst[maxn][maxn]; // Access tags 
int dir[4][2] = {
    0,1,0,-1,1,0,-1,0}; // The direction of the vector 
struct State{
    
    int x,y; // coordinates 
    int step; // Search step counter 
};
bool check(State s); // Constraint test function 
void bfs(); // Breadth first search 
int main(){
    
    memset(vst,false,sizeof(vst)); // Tag array initialization 
    bfs();
    cout << ans << endl;
    return 0;
}
bool check(State s){
    
    if(!vst[s.x][s.y] && s.step<=2020){
     // Coordinates are not accessed , And number of steps （ Time ） Less than or equal to 2020
        return true;
    }
    return false;
}

void bfs(){
    
    queue<State> q; //BFS queue 
    State now,next; // current state , Next state 
    vst[3000][3000]=vst[5020][3011]=vst[3011][3014]=vst[5000][5000]=true;
    next.x=3000,next.y=3000,next.step=0;
    q.push(next);
    next.x=5020,next.y=3011,next.step=0;
    q.push(next);
    next.x=3011,next.y=3014,next.step=0;
    q.push(next);
    next.x=5000,next.y=5000,next.step=0;
    q.push(next);
    while(!q.empty()){
    
        now = q.front();
        for (int i = 0; i < 4; ++i) {
    
            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];
            next.step = now.step+1;
            if(check(next)){
    
                q.push(next);
                vst[next.x][next.y] = true; // Tag access 
                ans++;
            }
        }
        q.pop(); // Out of the team 
    }
}

Output ：

20312088