双向BFS

小A和小B

题意：
小A和小B在n∗m迷宫的两个不同位置
迷宫中有障碍物迷宫中有障碍物
小A每分钟可以走周围八个方向一次小A每分钟可以走周围八个方向一次
小B每分钟可以走上下左右四个方向两次小B每分钟可以走上下左右四个方向两次
问两个人最早什么时候可以相遇，不能相遇输出-1问两个人最早什么时候可以相遇，不能相遇输出−1

第一行两个整数N，M分别表示迷宫的行和列。
接下来一个N×M的矩阵（1 < N，M < 1000）
其中"C"表示小A的位置,"D"表示小B的的位置，
"＃"表示不可通过的障碍，"."则是可以正常通过的位置。
字符用空格隔开

样例输入：

4 5
. . . . .
. # # # .
. . . # D
. . C # .

样例输出：

YES
3

题解：
将两个人的初始位置放入两个队列，记为第0秒
然后按各自的方向进行BFS搜索并分别记录下行走中可以到达的点，若其中一人目前走到的点是另一人曾经走过的，则说明他们俩必定相遇

代码：

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int n, m;
int dir[8][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
bool vis[2][1005][1005];
char s[1005][1005];

queue<pii> q[2];

bool bfs(int x){
  int sz = q[x].size();
  while(sz --){
    auto t = q[x].front();
    q[x].pop();
    for(int i = 0; i < 8 - 4 * x; i ++){
      int nx = t.first + dir[i][0];
      int ny = t.second + dir[i][1];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '#')
        continue;
      if(vis[1 - x][nx][ny])  return true;
      if(!vis[x][nx][ny]){
        q[x].push(make_pair(nx, ny));
        vis[x][nx][ny] = true;
      }
    }
  }
  return false;
}

int solve(){
  int ans = 0;
  while(!q[0].empty() || !q[1].empty()){
    ans ++;
    if(bfs(0))  return ans;
    if(bfs(1))  return ans;
    if(bfs(1))  return ans;
  }
  return -1;
}

int main()
{
  scanf("%d%d", &n, &m);
  getchar();
  memset(vis, false, sizeof(vis));
  for(int i = 0; i < n; i ++){
    for(int j = 0; j < m; j ++){
      scanf("%c", &s[i][j]);
      if(s[i][j] == 'C'){
        q[0].push(make_pair(i, j));
        vis[0][i][j] = true;
      }
      if(s[i][j] == 'D'){
        q[1].push(make_pair(i, j));
        vis[1][i][j] = true;
      }
      getchar();
    }
  }

  int ans = solve();
  if(ans == -1) puts("NO");
  else{
    puts("YES");
    printf("%d\n", ans);
  }
  return 0;
}

HDU-3085
题意：
有一个n∗m的矩阵，有三类东西
1.Z一秒可以扩散到两步以内的范围，每一步都可以走四个方向， 可以穿墙。
2.M一秒可以走3步， 每一步都可以是四个方向， 不可穿墙。
3.G一秒可以走1步， 每一步都可以是四个方向， 不可穿墙。
求M和G是否可以相遇。

题解：
双向BFS + 曼哈顿距离
由于Z可以穿墙， 所以对于整个图来说，Z畅通无阻， 因此可以利用曼哈顿距离来判断M和G是否会被抓到，避免了Z加入队列的麻烦。

代码：

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int t, n, m;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
char s[805][805];
bool vis[2][805][805];
int ans = 0;

pii G, M, Z[2];
queue<pii> q[2];

bool judge(int x, int y){
  if(x < 0 || x >= n || y < 0 || y >= m || s[x][y] == 'X')
    return false;
  if(abs(x - Z[0].first) + abs(y - Z[0].second) <= 2 * ans)
    return false;
  if(abs(x - Z[1].first) + abs(y - Z[1].second) <= 2 * ans)
    return false;
  return true;
}

bool bfs(int x){
  int sz = q[x].size();
  while(sz --){
    auto t = q[x].front();
    q[x].pop();
    if(!judge(t.first, t.second)) continue;
    for(int i = 0; i < 4; i ++){
      int nx = t.first + dir[i][0];
      int ny = t.second + dir[i][1];
      if(!judge(nx, ny))  continue;
      if(vis[1 - x][nx][ny]) return true;
      if(!vis[x][nx][ny]){
        q[x].push(make_pair(nx, ny));
        vis[x][nx][ny] = true;
      }
    }
  }
  return false;
}

int solve(){

  ans = 0;
  while(!q[0].empty())  q[0].pop();
  while(!q[1].empty())  q[1].pop();
  memset(vis, false, sizeof(vis));

  q[0].push(M);
  q[1].push(G);
  vis[0][M.first][M.second] = true;
  vis[1][G.first][G.second] = true;

  while(!q[0].empty() || !q[1].empty()){
    ans ++;
    if(bfs(0) == 1) return ans;
    if(bfs(0) == 1) return ans;
    if(bfs(0) == 1) return ans;
    if(bfs(1) == 1) return ans;
  }
  return -1;
}

int main()
{
  scanf("%d", &t);

  while(t --){
    int k = 0;
    scanf("%d%d",&n,&m);
    getchar();
    for(int i = 0; i < n; i ++){
      scanf("%s", s[i]);
      for(int j = 0; j < m; j ++){
        if(s[i][j] == 'M'){
          M = make_pair(i, j);
        }
        else if(s[i][j] == 'G'){
          G = make_pair(i, j);
        }
        else if(s[i][j] == 'Z'){
          Z[k ++] = make_pair(i, j);
        }
      }
      getchar();
    }
    int ans = solve();
    printf("%d\n", ans);
  }
  return 0;
}