Search - Luogu

1, Traversal of horses

Title Link: P1443 traversal of horse - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Title Description

There is an n * m chessboard. There is a horse at a certain point (x, y). You are required to calculate how many steps it takes for the horse to reach any point on the chessboard. (for the horse in Chinese chess, if you don't know how to walk, you can baidu.).

Input format

Enter only one line of four integers, n, m, x, y.

Output format

An n * m matrix represents how many steps the horse must take to reach a certain point (left aligned, 5 grids wide, output − 1 if it cannot reach).

Input and output samples

Enter #1

3 3 1 1

Output #1

0    3    2    
3    -1   1    
2    1    4    

Data scale

For all test points, guarantee 1 ≤ x ≤ n ≤ 400, 1 ≤ y ≤ m ≤ 400. 

BFS template questions can be written directly according to the template routine

Easy mistakes take a lot of time to debug

Initialize, dequeue, mark as passed, and update the number of steps

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N = 500;
const int dx[8] = {-1,1,-1,1,-2,2,-2,2};
const int dy[8] = {2,2,-2,-2,1,1,-1,-1};
int vis[N][N];
int step[N][N];

int main(){
    int n,m,sx,sy; cin >> n >> m >> sx >> sy;
    queue<PII> que;
    memset(step,-1,sizeof step); memset(vis,0,sizeof vis);
    vis[sx][sy] = 1, step[sx][sy] = 0;
    que.push({sx,sy});
    while(!que.empty()){
        PII temp = que.front(); que.pop();
        for(int i = 0; i < 8; i++){
            int nx = dx[i] + temp.first, ny = dy[i] + temp.second;
            if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) continue;
            step[nx][ny] = step[temp.first][temp.second] + 1;
            que.push({nx,ny});
            vis[nx][ny] = 1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            printf("%-5d",step[i][j]);
        printf("\n");
    }
    return 0;
}

2, What a strange game

Title Link: P1747 what a strange game - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Title Description

Love and sorrow are bored on the bus, so they play with their mobile phones. A strange game entered the eyes of the great God of love and sorrow: * * * (the name of the game was mosaic). This game is similar to chess, but only one black and white horse at points x1,y1 and x2,y2. They have to go from points x1,y1 and x2,y2 to 1,1. The difference between this game and ordinary chess is that horses can walk "day" or "field" like elephants. Now the God of love and sorrow wants to know the minimum steps of two horses to 1,1. Can you help him solve this problem?

Input format

Line 1: two integers x1, y1

Line 2: two integers x2, y2

Output format

Line 1: steps from dark horse to 1,1

Line 2: steps from white horse to 1,1

Input and output samples

Enter #1

12 16
18 10

Output #1

8 
9

Data range

100% data: x1, Y1, X2, Y2 < = 20

Or bfs, but for the first question, it becomes 12 directions, and then search the answers of two points twice

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N = 60;
const int dx[] = {-1,1,-1,1,-2,2,-2,2,2,2,-2,-2};
const int dy[] = {2,2,-2,-2,1,1,-1,-1,-2,2,-2,2};

int vis[N][N];

struct Node {
    int x, y, step;
    Node(int x, int y, int step){
        this->x = x;
        this->y = y;
        this->step = step;
    }
};

int bfs(int sx, int sy){
    queue<Node> que;
    que.push(Node(sx, sy, 0));
    vis[sx][sy] = 1; 
    while(!que.empty()){
        int x = que.front().x, y = que.front().y, step = que.front().step;
        que.pop();
        for(int i = 0; i < 12; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > 50 || ny < 1 || ny > 50 || vis[nx][ny]) continue;
            if(nx == 1 && ny == 1) return step + 1;
            que.push(Node(nx, ny, step + 1));
            vis[nx][ny] = 1;
        }
    }
}

int main(){
    int sx,sy;
    cin >> sx >> sy;
    cout << bfs(sx,sy) << endl;
    memset(vis,0,sizeof(vis));
    cin >> sx >> sy;
    cout << bfs(sx,sy) << endl;
    return 0;
}

3, Leave Zhongshan Road

Title Link: P1746 leave Zhongshan Road - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Title Description

After shopping, the great God of love and sorrow plans to leave Zhongshan Road by car. Now the great God of love and sorrow is at X1 and Y1, and the station is at x2 and Y2. Now give an n × N (n < = 1000), 0 represents the road, 1 represents the shop (can't cross from the shop), and the great God of love and sorrow can only travel on the road vertically or horizontally. In order to save time, the God of love and sorrow requires the shortest distance to the destination (a[i][j] distance is 1). Can you help him solve it?

Input format

Line 1: a number n

Line 2 ~ line n+1: description of the whole map (0 indicates the road and 1 indicates the shop. Note that there is no space between the two numbers)

Line n+2: four numbers x1,y1,x2,y2

Output format

Only 1 line: shortest distance to destination

Input and output samples

Enter #1 copy

3
001
101
100
1 1 3 3

Output #1

4

Data range

20% data: n < = 100

100% data: n < = 1000

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N = 1e3+10;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};


int vis[N][N];
int step[N][N];
char g[N][N];
int n, sx, sy, ex, ey;; 

int bfs(){
    queue<PII> que;
    que.push({sx,sy});
    vis[sx][sy] = 1;
    while(!que.empty()){
        int x = que.front().first, y = que.front().second;
        que.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny] || g[nx][ny] == '1') continue;
            vis[nx][ny] = 1;
            que.push({nx,ny});
            step[nx][ny] = step[x][y] + 1; 
            if(nx == ex && ny == ey) return step[nx][ny];
        }
    }
    return -1;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> g[i][j];
    cin >> sx >> sy >> ex >> ey;

    cout << bfs() << endl;
    return 0;
}

4, Game between Mzc and male servants

Title Link: P2298 game between MZC and men - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Title Description

mzc family is very rich (joking), and his family has n male servants (everyone who has played the last game knows). He gathered them together and they decided to play hide and seek. Now mzc I'm looking for his male servant. Let's help!

Due to the small number of male servants and mzc great ability to find people [laopo], only one male servant needs to be found at a time.

Input format

The first row has two numbers n, m, indicating that there are n rows and m columns for male servants to hide,

After that, the matrix of n rows and m columns,'m 'represents mzc,'d' represents male servants, '#' represents unable to leave, '‘ Indicates open space.

Output format

One line, if there is a solution: output a number step, indicating the shortest number of moves to find a male servant.

If there is no solution: output "No Way!".

Input and output samples

Enter #1

5 6
.#..#.
....#.
d.....
#####.
m.....

Output #1

12

Data range

3 < = m, n <= 2000

Because mzc Da is very anxious, he can only wait for 1S.

Record the starting point and ending point, and change the template

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N = 2e3+10;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int vis[N][N];
char g[N][N];
int n, m, sx, sy, ex, ey;; 

struct Node {
    int x, y, step;
    Node(int x, int y, int step){
        this->x = x;
        this->y = y;
        this->step = step;
    }
};

int bfs(){
    queue<Node> que;
    que.push(Node(sx, sy, 0));
    vis[sx][sy] = 1;
    while(!que.empty()){
        int x = que.front().x, y = que.front().y, step = que.front().step;
        que.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || g[nx][ny] == '#') continue;
            vis[nx][ny] = 1;
            que.push(Node(nx, ny, step + 1));
            if(nx == ex && ny == ey) return step + 1;
        }
    }
    return -1;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
            if(g[i][j] == 'm') sx = i, sy = j;
            if(g[i][j] == 'd') ex = i, ey = j;
        }

    int ans = bfs();
    if(ans == -1) cout<<"No Way!"<<endl;
    else cout << ans << endl;
    return 0;
}

5, Bloody Vanguard

Title Link: P1332 blood vanguard - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Title Description

The Legion is a matrix with nn rows and mm columns, and each unit is a member of the blood pioneer army. People infected with the plague will spread the plague around every hour until all people are infected with the plague. You have mastered the location of the source of infection. Your task is to calculate the time when the Lords of the blood pioneer army were infected with the plague and report it to the Lich King, so as to carry out a round of targeted encirclement and suppression of the blood pioneer army.

Input format

Row 11: four integers nn, mm, aa, bb, indicating that the Legion matrix has nn rows and mm columns. There are aa infection sources, bb is the number of Lords in the bloody death squads.

Next line aa: each line has two integers xx and yy, indicating that the infection source is in line xx and column yy.

Next bb line: each line has two integers xx and yy, indicating that the position of the Lord is in line xx and column yy.

Output format

Lines 11 to bb: an integer in each line indicates the time when the LORD was infected with the plague. The output order is consistent with the input order. If a person's location is at the source of infection, the time when he is infected with the plague is 00.

Input and output samples

Enter #1

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

Output #1

3
1
3

Description / tips

Input / output example 1 explanation

The following figure shows the time when everyone was infected with the plague and the location of the infection source and Lord.

Data scale and agreement

For 100% data, ensure 1 ≤ n, m ≤ 500, 1 ≤ a, B ≤ 105.

code1: the sample of explosive search trick card has been optimized by 19000

code2: one of the basic search types. Add all virus origins to the queue, and then expand the search.

code1

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int inf = 1e9;
const int N = 1e3+10;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};


int vis[N][N];
int g[N][N];
int n, m, a, b;
int flag = 1;

void bfs(int sx, int sy){
    queue<PII> que;
    que.push({sx,sy});
    vis[sx][sy] = 1;
    int count = 0;
    while(!que.empty() && count < 19000){
        count++;
        int x = que.front().first, y = que.front().second;
        que.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny] == flag) continue;
            vis[nx][ny] = flag;
            que.push({nx,ny});
            g[nx][ny] = min(g[nx][ny], g[x][y] + 1);
        }
    }
}

int main(){
    cin >> n >> m >> a >> b;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            g[i][j] = inf;
        }
    }

    int tx, ty;
    for(int i = 0; i < a; i++){
        cin >> tx >> ty;
        g[tx][ty] = 0;
        bfs(tx, ty);
        flag++;//Mark whether it has been searched this time
    }

    for(int i = 0; i < b; i++){
        cin >> tx >> ty;
        cout << g[tx][ty] << endl;
    }
    return 0;
}

code2:

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>

#define debug cout << "___debug___\n"; 
using namespace std;

typedef pair<int,int> PII;
const int inf = 1e9;
const int N = 1e3+10;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

struct Node {
    int x, y, step;
    Node(int x, int y, int step){
        this->x = x;
        this->y = y;
        this->step = step;
    }
};

int vis[N][N];
int g[N][N];
int n, m, a, b;
int flag = 1;
queue<Node> que;

void init(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            g[i][j] = inf;
        }
    }
}

void bfs(){
    while(!que.empty()){
        int x = que.front().x, y = que.front().y, step = que.front().step;
        que.pop();
        g[x][y] = min(g[x][y], step);
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            que.push(Node(nx, ny, step + 1)); 
        }
    }
}

int main(){
    cin >> n >> m >> a >> b;
    init();
    int tx, ty;
    for(int i = 0; i < a; i++){
        cin >> tx >> ty;
        que.push(Node(tx,ty,0));
        g[tx][ty] = 0;
        vis[tx][ty] = 1;
    }
    bfs();
    for(int i = 0; i < b; i++){
        cin >> tx >> ty;
        cout << g[tx][ty] << endl;
    }
    return 0;
}

6, Find the number of cells

Title Link: P1451 finding the number of cells - New Ecology of computer science education in Luogu (luogu.com.cn)

Title Description

A rectangular array is composed of numbers 0 to 9. Numbers 1 to 9 represent cells. Cells are defined as the same cell along the cell number. Calculate the number of cells in a given rectangular array.

Input format

The two integers in the first row represent the matrix sizes n and m.

The next N lines, each with a string of length m containing only characters 0 to 9, represent this n × Matrix of M.

Output format

An integer in a row represents the number of cells.

Input and output samples

Enter #1

4 10
0234500067
1034560500
2045600671
0000000089

Output #1

4

Description / tips

Data scale and agreement

For 100% data, ensure 1 ≤ N and m ≤ 100.

In fact, it is to find how many blocks there are, so we can search his compatriots for each cell we haven't visited

#include<iostream>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>

#define debug cout << "___debug___\n"; 
using namespace std;

typedef pair<int,int> PII;
const int inf = 1e9;
const int N = 1e2+10;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int vis[N][N];
char g[N][N];
int n, m, ans;
queue<PII> que;

void bfs(int sx, int sy){
    ans ++;
    que.push({sx,sy}); 
    vis[sx][sy] = 1;
    while(!que.empty()){
        int x = que.front().first, y = que.front().second;
        que.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || g[nx][ny] == '0') continue;
            vis[nx][ny] = 1;
            que.push({nx, ny}); 
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(g[i][j] != '0' && !vis[i][j]) bfs(i, j);//Remember to judge whether the cell has been visited, otherwise it will repeat a lot
        }
    }
    cout << ans << endl;
    return 0;
}