我们都知道BFS搜索的时间复杂度为$O(N^2)$。

而双向BFS搜索因为是从两边开始搜索,时间复杂度会优化很多,为朴素BFS的时间复杂度开根号。

下面请看模板代码。

输入样例:

1
2
3
4
5
6
5 5
..###
#....
#.#.#
#.#.#
#.#..
1
9
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
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

int n, m;
char a[55][55];
int nextn[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int dis[55][55], vst[55][55];

struct Node {
int x, y;
};

int main() {
cin >> n >> m;

memset(a, 0, sizeof(a));
memset(dis, 0, sizeof(dis));
memset(vst, 0, sizeof(vst));

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}

queue<Node> que1; // 向前搜
queue<Node> que2; // 向后搜

// vst标记状态 dis表示路程
que1.push(Node{1, 1}), dis[1][1] = 1, vst[1][1] = 1;
que2.push(Node{n, m}), dis[n][m] = 1, vst[n][m] = 2;

while (!que1.empty() && !que2.empty()) {
int flag;
Node head;
if (que1.size() > que2.size()) { // 哪个队列元素少就从哪个队列开始搜
head = que2.front(); // 向前搜
que2.pop();
flag = 2;
} else {
head = que1.front(); // 向后搜
que1.pop();
flag = 1;
}

for (int i = 0; i < 4; i++) {

int tx = head.x + nextn[i][0];
int ty = head.y + nextn[i][1];

if (tx > n || ty > m || tx <= 0 || ty <= 0) continue;

if (a[tx][ty] == '.') {
if (!dis[tx][ty]) { // 这一步没有队列走过
dis[tx][ty] = dis[head.x][head.y] + 1; // 路程加一
vst[tx][ty] = vst[head.x][head.y]; // 继承状态
if (flag == 1) que1.push(Node{tx, ty});
else if (flag == 2) que2.push(Node{tx, ty});
} else if (vst[head.x][head.y] + vst[tx][ty] == 3) { // 如果相遇
cout << dis[head.x][head.y] + dis[tx][ty] << endl; // 步数相加
return 0;
}
}
}
}

return 0;
}

评论