POJ - 2243 双向BFS

发表于 | 阅读次数：

双向BFS是从起点和终点两边扩展节点，当节点重合即为最优解。

对于双向BFS，我们逐层求解，有两个队列，当我们遍历完毕这个队列的这一层，然后就要遍历另一个队列的相同的层数。

POJ - 2243

Knight moves

思路

起点和终点只是一个二维坐标，因此用vis数组存储即可。从起点和终点分别维护一个队列，开始扩展，当两者重合即为最终答案。一遍过，还是有点兴奋，逐渐的会加大这种题型的难度。

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
struct node{
   int x,y;
};
int x1, y1, x2, y2;
bool vis[2][10][10];
queue<node>Q[2];
int dir[8][2] = {{2, 1}, {2 ,-1},{-2, 1},{-2 ,-1}, {1 ,2},{1, -2},{-1, 2},{-1, -2}};
int bfs(int id)
{
    int sz = Q[id].size();
    while(sz--)
    {
        node p = Q[id].front();
        Q[id].pop();
        for(int i = 0; i < 8; ++i)
        {
            int xx = p.x + dir[i][0];
            int yy = p.y + dir[i][1];
            if(xx < 0 || xx > 7 || yy < 0 || yy > 7 || vis[id][xx][yy]) continue;
            vis[id][xx][yy] = 1;
            Q[id].push({xx, yy});
            if(vis[!id][xx][yy])
                return 1;
        }
    }
    return 0;
}
int solve()
{
    while(!Q[0].empty())
        Q[0].pop();
    while(!Q[1].empty())
        Q[1].pop();
    vis[0][x1][y1] = 1;
    vis[1][x2][y2] = 1;
    Q[0].push({x1, y1});
    Q[1].push({x2, y2});
    int step = 0;
    while(!Q[0].empty() || !Q[1].empty())
    {
        int num1 = bfs(0);
        step++;
        if(num1)  return step;
        int num2 = bfs(1);
        step++;
        if(num2)  return step;
    }
    return -1;
}
int main()
{
    string s, s1;
    while(cin >> s >> s1){
        if(s == s1)
        {
            cout << "To get from "<< s << " to " << s1 << " takes " << 0 << " knight moves." << '\n';
            continue;
        }
        memset(vis ,0 ,sizeof(vis));
        x1 = s[0] - 'a';
        x2 = s1[0] - 'a';
        y1 = s[1] - '1';
        y2 = s1[1] - '1';
        cout << "To get from "<< s << " to " << s1 << " takes " << solve() << " knight moves." << '\n';
}
}