双向BFS
-
双向BFS我们可以看作是一般BFS的增强版。
-
我们可以把BFS想象成在一个平静的池塘中丢一颗石头，激起的波浪一层层扩散到整个空间，知道到达边界或目标状态，类比搜索就是得到了从起点到目标点的最优解。那么，我们可不可以考虑丢两块石头下去呢，一个在起点，一个在终点，同时向对方扩散，那么两个的波一定会在某个位置相交，此时就是最优解。
-
同理，我们进行BFS可以从起点和终点同时开始，相遇即最优解。双向BFS与一般BFS相比空间上会是少很多，从而更有效率。
我们有两种搜索方法：
- 两个方向交替扩展。
- 选择节点个数较少的那个方向先扩展。
-
相比较两种方法，方法2 为只需要略加修改控制结构，每次while循环时只扩展正反两个方向中结点数目较少的那一个，可以时两边的发展速度保持一定的平衡，从而减少总扩展结点的个数，加快搜索速度。
-
所以，很明显 方法2 要优于 方法1。
【例题】噩梦
题解
-
由于是男孩和女孩同时移动，而不是只有一个人移动，所以这题要用双向广搜。
-
我们在bfs中按时间t从 1开始枚举。
-
如果男孩和女孩都不能再继续扩展，则跳出枚举。
-
对于男孩，每次扩展三步，并标记扩展到的格子。
-
如果某个能扩展的格子被女孩扩展过，那么直接返回现在的时间。
-
对于女孩，每次扩展一步，并标记扩展到的格子。
-
如果某个能扩展的格子被男孩扩展过，那么直接返回现在的时间。
-
对于鬼，由于鬼是无视墙的，所以我们只需要在扩展男孩和女孩的时候，判断下有没有进入鬼的占领范围即可。
-
题目中已经给出了，在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。
-
我们在第t秒扩展的时候，判断被扩展的格子是否与某个鬼的曼哈顿距离小于2t即可。
-
详见代码及注释
-
时间复杂度
-
每个格子最多只会被扩展一次（如果被扩展了两次，男孩和女孩就会合惹~）
-
一共有T组测试数据，每组测试数据的地图有 N×M 个格子，
-
所以时间复杂度是 O(TNM)
//DC Songxingan
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define pii pair<int, int>
using namespace std;
int n, m;
int T;
char a[810][810];
int reach[810][810]; //统计可达性，男孩为1，女孩为2
pii girl, boy, z[3]; //男孩、女孩、两个鬼的位置
int dis(int x1, int y1, int x2, int y2)
{
return abs(x1 - x2) + abs(y1 - y2);
}
bool check(int x, int y, int t)
{
if (a[x][y] == 'X' || x > n || x < 1 || y < 1 || y > n)
return 0;
if (dis(x, y, z[1].first, z[1].second) <= 2 * t)
return 0;
if (dis(x, y, z[2].first, z[2].second) <= 2 * t)
return 0;
return 1;
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int bfs()
{
int gh = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 'M')
{
boy.first = i;
boy.second = j;
}
if (a[i][j] == 'G')
{
girl.first = i;
girl.second = j;
}
if (a[i][j] == 'Z')
{
gh++;
z[gh].first = i;
z[gh].second = j;
}
}
}
queue<pii> qb, qg;
qb.push(boy);
qg.push(girl);
int step = 0;
while (qb.size() || qg.size())
{
step++;
for (int t = 1; t <= 3; t++)
{ //男孩每步相当于bfs三次
int sz = qb.size();
for (int j = 1; j <= sz; j++)
{
int x = qb.front().first;
int y = qb.front().second;
qb.pop();
if (!check(x, y, step))
continue;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (reach[nx][ny] == 1)
continue;
if (!check(nx, ny, step))
continue;
if (reach[nx][ny] == 2)
return step;
reach[nx][ny] = 1;
qb.push(make_pair(nx, ny));
}
}
}
int sz = qg.size();
for (int j = 1; j <= sz; j++)
{
int x = qg.front().first;
int y = qg.front().second;
qg.pop();
if (!check(x, y, step))
continue;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (reach[nx][ny] == 2)
continue;
if (!check(nx, ny, step))
continue;
if (reach[nx][ny] == 1)
return step;
reach[nx][ny] = 2;
qg.push(make_pair(nx, ny));
}
}
}
return -1;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
memset(reach, 0, sizeof(reach));
printf("%d\n", bfs());
}
return 0;
}
