POJ 1915 Knight Moves 双向BFS

Description

给出起点终点，按图示方法走，至少要几步

双向BFS

交替逐层搜索√

交替节点搜索×

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n;
struct node
{
    int x, y;
};
queue<node> q[2];
bool vis[2][305][305];
int dx[] = { 1, 2, 1, 2, -1, -2, -1, -2 };
int dy[] = { 2, 1, -2, -1, 2, 1, -2, -1 };


bool BFS(int num)
{
    int sz = q[num].size();
    while(sz--)
    {
        node first = q[num].front();
        q[num].pop();
        for(int i = 0; i < 8; ++i)
        {
            int xx = first.x + dx[i];
            int yy = first.y + dy[i];
            if(xx < 0 || yy < 0 || xx >= n || yy >= n || vis[num][xx][yy])
                continue;
            vis[num][xx][yy] = 1;
            q[num].push({xx, yy});
            if(vis[!num][xx][yy])
                return 1;
        }
    }
    return 0;
}

int slove(int sx, int sy, int ex, int ey)
{
    memset(vis, 0, sizeof(vis));
    while(q[0].size())
        q[0].pop();
    while(q[1].size())
        q[1].pop();
    vis[0][sx][sy] = 1;
    vis[1][ex][ey] = 1;
    q[0].push({sx, sy});
    q[1].push({ex, ey});
    int step = 0;
    while(q[0].size() || q[1].size())
    {
        bool flag = BFS(0);
        step++;
        if(flag)
            return step;
        flag = BFS(1);
        step++;
        if(flag)
            return step;
    }
    return -1;
}

int main()
{
    int t, sx, sy, ex, ey;
    cin >> t;
    while(t--)
    {
        cin >> n;
        cin >> sx >> sy >> ex >> ey;
        if(sx == ex && sy == ey)
            cout << '0' << '\n';
        else
            cout << slove(sx, sy, ex, ey) << '\n';
    }
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

代码参考 https://yuntengzhiyu.github.io/2019/06/02/POJ-2243-%E5%8F%8C%E5%90%91BFS/