宣传一下$\Huge\color{skyblue}{USACO}$月赛打卡活动题解汇总

第一种方法：暴力BFS
这样会TLE！

#include <bits/stdc++.h>
using namespace std;
int a[1010][1010], n, x, y;
map< pair<int, int>, int> m;
priority_queue< pair< int, pair<int, int> > > q;
int shang = 0x3f3f3f3f, xia = -0x3f3f3f3f, zuo = 0x3f3f3f3f, you = -0x3f3f3f3f;
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int main() {
    scanf("%d%d%d", &n, &x, &y);
    for (int i = 1;i <= n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        m[make_pair(a, b)] = 1;
        shang = min(shang, a);
        xia = max(xia, a);
        zuo = min(zuo, b);
        you = max(you, b);
    }
    a[x][y] = 1;
    q.push(make_pair(0, make_pair(x, y)));
    int ans = 0x3f3f3f3f;
    while (q.size()) {
        pair<int, pair<int, int> > f = q.top(); q.pop();
        int A = f.second.first, B = f.second.second;
        if (A == shang || A == xia || B == zuo || B == you) ans = min(ans, a[A][B]);
        for (int i = 0;i < 4; i++) {
            int xx = A + dx[i], yy = B + dy[i];
            if (xx < shang || xx > xia || yy < zuo || yy > you) continue;
            if (a[xx][yy]) continue;
            if (m[make_pair(xx, yy)]) a[xx][yy] = a[A][B] + 1;
            else a[xx][yy] = a[A][B];
            q.push(make_pair(-a[xx][yy], make_pair(xx, yy)));
        }
    }
    printf("%d\n", ans - 1);
    return 0;
}

这时候我们就要采取第二种方法：双向BFS

用双端队列做：

#include <bits/stdc++.h>
using namespace std;
int g[1010][1010], dist[1010][1010];
bool st[1010][1010];
int n, x, y, xx, yy;
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; // 上下左右
void bfs(int x, int y) {
    deque< pair<int, int> > q; q.push_front(make_pair(x, y));
    st[x][y] = 1; dist[x][y] = 0;
    while (q.size()) {
        pair<int, int> t = q.front();
        q.pop_front();
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a < 0 || a > xx || b < 0 || b > yy) continue;
            if(st[a][b]) continue;
            if(g[a][b] == 1) {
                dist[a][b] = dist[t.first][t.second] + 1;
                q.push_back(make_pair(a, b));
            } else {
                dist[a][b] = dist[t.first][t.second];
                q.push_front(make_pair(a, b));
            }
            st[a][b] = 1;
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &x, &y);
    xx = x + 1, yy = y + 1;
    for (int i = 1;i <= n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        g[a][b] = 1;
        xx = max(xx, a + 1); yy = max(yy, b + 1);
    }
    bfs(x, y);
    printf("%d", dist[0][0]);
}