这个注意真的厉害，如果没有将这一层的全部poll出来，最后一个样例不能通过

但是 qb存储多余两层的元素，会对最短距离造成影响 这是为啥会有影响？

老哥能不能给我示范一下acwing1102的双向广搜咋写呀，总是写不好哈哈

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 310, INF = 0x3f3f3f3f;

int n;
int g[N][N];
int dist1[N][N], dist2[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
PII start, ed;

int extend(queue<PII>& q1, queue<PII>& q2, int dist1[N][N], int dist2[N][N])
{
    int len = q1.size();
    for(int u = 0;u < len;u ++)
    {
        PII t = q1.front();
        q1.pop();

        for(int i = 0;i < 8;i ++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n) continue;
            if(dist1[a][b] != -1) continue;
            q1.push({a, b});
            dist1[a][b] = dist1[t.x][t.y] + 1;
            if(dist2[a][b] != -1) return dist1[a][b] + dist2[a][b];
        }
    }
    return INF;
}
int bfs()
{
    memset(dist1, -1, sizeof dist1);
    memset(dist2, -1, sizeof dist2);

    if(start.x == ed.x && start.y == ed.y) return 0;//特判

    queue<PII> q1, q2;
    q1.push({start.x, start.y});
    q2.push({ed.x, ed.y});

    dist1[start.x][start.y] = 0;
    dist2[ed.x][ed.y] = 0;

    int t;
    while(q1.size() && q2.size())
    {

        if(q1.size() <= q2.size())
        {
            t = extend(q1, q2, dist1, dist2);
        }
        else t = extend(q2, q1, dist2, dist1);

        if(t != INF) return t;
    }
    return t;
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n;
        int a, b;
        cin >> a >> b;
        start = {a, b};
        cin >> a >> b;
        ed = {a, b};
        cout << bfs() << endl;
    }
}

能帮我看一下我写的这个哪里效率低吗，超时了

#include <iostream>
#include <queue>
#include <unordered_map>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
int res = 0;

bool extend(queue<PII>& h, unordered_map<string, int>& h1, unordered_map<string, int>& h2, int size)
{
    int addx[8] = { 1,1,-1,-1,2,2,-2,-2 };
    int addy[8] = { 2,-2,2,-2,1,-1,1,-1 };   
    queue<PII> temp;
    while(h.size())
    {
        auto item = h.front();
        h.pop();
        int dx = item.first; int dy = item.second;
        string t = to_string(dx) + "*" + to_string(dy);
        if(h2.count(t)) return true;
        for(int i = 0; i < 8; i++)
        {
            int newx = addx[i] + dx; int newy = addy[i] + dy;
            if(newx < 0 || newy < 0) continue;
            if(newx > size || newy > size) continue;
            string s = to_string(newx) + "*" + to_string(newy);
            if(h1.count(s)) continue;
            temp.push({newx, newy});
            h1[s] = 1;
        }
    }
    res++;
    swap(h, temp);
    return false;
}

int minKnightMoves(int size, int fx, int fy, int x, int y)
{
    res = 0;
    if(fx == x && fy == y) return 0;
    queue<PII> head, tail;
    unordered_map<string, int> hash1, hash2;
    head.push({fx, fy}); tail.push({x, y});

    while(head.size() && tail.size())
    {
        bool flag = false;
        if(head.size() > tail.size())
            flag = extend(tail, hash2, hash1, size);
        else
            flag = extend(head, hash1, hash2, size);

        if(flag) return res;
    }
    return -1;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int size, fx, fy, sx, sy;
        scanf("%d%d%d%d%d", &size, &fx, &fy, &sx, &sy);
        int n = minKnightMoves(size, fx, fy, sx, sy);
        cout << n << endl;
    }
    return 0;
}

感觉没什么错，可能是map的问题，也可能是string构造的次数太多

感谢小呆呆老师

有这么几点建议供参考：
1. unorder_map改为map试试，前者最坏情况会退化为O(n)
2. string的构造次数太多
3. x.count()的复杂度是O(n)的，前面改为map后可以用[]来引用，稳定log级别的，或者采用数组记忆化的方式，像我开个二维数组那样
4. swap()的复杂度不是很了解，如果是O(n)的话就很糟糕了，可以通过记录队列大小的方式把这个地方优化掉
暂且改进下这几点试试吧

建议不要一开始就重度依赖STL，先明确相应操作的复杂度会是你更好的利用STL

谢谢， 查找某个值的时候unordered_map效率好像比map要高吧， 如果不构造string 改成 map[HTML_REMOVED]> hash 这样排除重复还是过不了， swap复杂度我也不是很了解不过LeetCode上好几个题双向BFS 我都用的swap，都是速度100%， count那个可能有问题我打算考完试之后再弄弄哈哈