洛谷P1443 马的遍历（bfs模版题）

洛谷P1443

马的遍历

https://www.luogu.com.cn/problem/P1443

一道经典的bfs入门题

这里贴上代码

//#define LOCAL 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
//#define int long long
#define endl "\n";
using namespace std;
const int maxn = 500;
int G[maxn][maxn], m, n, x, y;
bool discovery[maxn][maxn];
const int dx[8] = { -1,-2,-2,-1,1,2,2,1 };
const int dy[8] = { 2,1,-1,-2,2,1,-1,-2 };
struct node {
    int x, y;
};
void bfs(int x, int y) {
    queue<node> F;
    F.push({ x,y });
    G[x][y] = 0;
    discovery[x][y] = true;
    while (!F.empty()) {
        int u = F.front().x;
        int v = F.front().y;
        F.pop();
        for (int i = 0; i < 8; i++) {
            int cx = u + dx[i];
            int cy = v + dy[i];
            if (cx <= 0 || cy <= 0 || cx > n || cy > m || discovery[cx][cy]) continue;
            F.push({ cx,cy });
            G[cx][cy] = G[u][v] + 1;
            discovery[cx][cy] = true;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("stdin", "r", stdin);
    freopen("stdout", "w", stdout);
#endif
    cin >> n >> m >> x >> y;
    memset(G, -1, sizeof(G));
    memset(discovery, false, sizeof(discovery));
    bfs(x, y);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%-5d", G[i][j]);
        }
        printf("\n");
    }
    return 0;
}
这里用PII也可以，本人偏好结构体

（在洛谷看更好）

这是一道经典的bfs模版题

但是有一些需要注意的点

这里不说题目本身，因为不是很难

这里说一下我发现的问题

数组下标从1开始还是从0开始一定要统一，因为大部分人一开始学习的都是下标从0开始

所以一开始用1作为第一个下标的时候可能会混，这一点要注意

下一个就是不要混用printf和cout

这里引用一篇博客

https://blog.csdn.net/ltx06/article/details/14434519

这篇博客中讲了加速流为什么会导致混用printf和cout时会出现输出顺序不一样的结果