BFS习题课(上)

BFS习题课(上)

题目一

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

typedef pair<int,int> PII;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
const int N = 1010;

int n;
queue<PII> q;
char g[N][N];
int dist[N][N];
int s_x,s_y;
int z_x,z_y;

int bfs(int x,int y) {
    memset(dist,-1,sizeof dist);
    q.push({x,y});
    dist[x][y] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a < 1 || a > n || b < 1 || b > n) continue;
            if (dist[a][b] > 0) continue;
            if (g[a][b] == '1') continue;
            q.push({a,b});
            dist[a][b] = dist[t.first][t.second] + 1;
            if (a == z_x && b == z_y) return dist[a][b];
        }
    }
    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 >> s_x >> s_y >> z_x >> z_y;
    int res = bfs(s_x,s_y);
    cout << res;
}

题目二

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

typedef pair<int,int> PII;

int dx[] = {1,-1,1,-1,2,-2,2,-2};
int dy[] = {2,2,-2,-2,1,1,-1,-1};

const int N = 410;
int n,m;
int s_x,s_y;
int dist[N][N];
queue<PII> q;
void bfs(int x,int y) {
    memset(dist,-1,sizeof dist);
    q.push({x,y});
    dist[x][y] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 8;i++) {
            int a = t.first+dx[i];
            int b = t.second+dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] >= 0) continue;
            q.push({a,b});
            dist[a][b] = dist[t.first][t.second] + 1;
        }

    }
}
int main () {
    cin >> n >> m >> s_x >> s_y;
    bfs(s_x,s_y);
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

题目三

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

typedef pair<int,int> PII;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int n,m;
int dist[510][510];

queue<PII> q;
//int jj[510][510];
int g,j;
vector<PII> jj;


void bfs() {
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] >= 0) continue;
            q.push({a,b});
            dist[a][b] = dist[t.first][t.second] + 1;
        }
    }
}
int main () {
    memset(dist,-1,sizeof dist);
    cin >> n >> m >> g >> j;
    for (int i = 1;i <= g;i++) {
        int a,b;
        cin >> a >> b;
        q.push({a,b});
        dist[a][b] = 0;
    }
    for (int i = 1;i <= j;i++) {
        int a,b;
        cin >> a >> b;
        jj.push_back({a,b});
    }
    bfs();
    for (auto t:jj) {
        cout << dist[t.first][t.second] << endl;
    }
}

题目四

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

typedef pair<int,int> PII;


int dx[] = {1,1,-1,-1,2,2,-2,-2,-2,-2,2,2};
int dy[] = {2,-2,2,-2,1,-1,1,-1,2,-2,2,-2};


int res;
int dist[50][50];
int n,m;
int bfs(int x,int y) {
    queue<PII> q;
    q.push({x,y});
    memset(dist,-1,sizeof dist);
    dist[x][y] = 0;

    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 12;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a < 1 || b < 1) continue;
            if (dist[a][b] >= 0) continue;
            q.push({a,b});
            dist[a][b] = dist[t.first][t.second] + 1;
            if (a == 1 && b == 1) return dist[a][b];
        }
    }
}
int main () {

    cin >> n >> m;
    res = bfs(n,m);
    cout << res << endl;
    cin >> n >> m;
    res = bfs(n,m);
    cout << res << endl;
}

题目五

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

#define x first
#define y second
typedef pair<int,int> PII;
const int N = 35;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int n;
int g[N][N];
int st[N][N];
queue<PII> q;
void bfs(int x,int y) {
    q.push({x,y});
    st[x][y] = 1;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a < 0 || a > n+1 || b < 0 || b > n + 1) continue;
            if (g[a][b] == 1) continue;
            if (st[a][b]) continue;
            q.push({a,b});
            st[a][b] = 1;
        }
    }
}
int main () {
    cin >> n;
    int st_x,st_y;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> g[i][j];


        }
    }
    //if (ans)
        bfs(0,0);
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (g[i][j] == 0 && !st[i][j]) g[i][j] = 2;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
}

题目六

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

#define x first
#define y second
typedef pair<int,int> PII;
const int N = 310;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int st[N][N];
int dist[N][N];
int n;
queue<PII> q;
int bfs(int x,int y) {
    //memset(dist,-1,sizeof dist);
    q.push({x,y});
    dist[x][y] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a < 0 || b < 0) continue;
            if (dist[a][b]) continue;
            if (dist[t.first][t.second] + 1>= st[a][b]) continue;
            dist[a][b] = dist[t.first][t.second] + 1;
            q.push({a,b});
            if (st[a][b] > 1e9) return dist[a][b];
        }
    }
    return -1;
}
int main () {
    cin >> n;
    memset(st,0x3f,sizeof st);
    for (int i = 1;i <= n;i++) {
        int x,y,t;
        cin >> x >> y >> t;
        st[x][y] = min(st[x][y],t);
        for (int i = 0;i < 4;i++) {
            int a = x+dx[i],b = y+dy[i];
            if (a < 0 || a > 301 || b < 0 || b > 301) continue;
            st[a][b] = min(st[a][b],t);
        }

    }

    int res = bfs(0,0);

    cout << res;
}