[每日一题] [NC23486] 小A与小B

题目大意：一个迷宫里面有src和dst，src每次可以八个方向走一步，dst每次可以走两次，每次只能四个方向，不能走障碍物上。问最少多少次可以相遇。注意可以原地不动。

https://ac.nowcoder.com/acm/problem/23486

这题比较标准的双向BFS，注意可以原地不动。比如考虑这个case:

A #
# B

应该要输出1，而不是NO

#define MAXN 2000
int N,M;
char grid[MAXN][MAXN];

VPII src_dirs={
  {-1,-1},
  {-1,0},
  {-1,1},
  {0,-1},
  {0,1},
  {1,-1},
  {1,0},
  {1,1},
};
int src_dist[MAXN][MAXN];
int dst_dist[MAXN][MAXN];

int doit() {
  PII src={-1,-1}, dst={-1,-1};
  REP(i,N){
    REP(j,M){
      if(grid[i][j]=='C'){
        src={i,j};
        src_dist[i][j]=1;
      }
      if(grid[i][j]=='D'){
        dst={i,j};
        dst_dist[i][j]=1;
      }
    }
  }
  VPII src_layer;
  VPII dst_layer;
  src_layer.PB(src);
  dst_layer.PB(dst);
  int l = 0;
  while (!src_layer.empty() || !dst_layer.empty()) {
    ++l;
    VPII tmp_src, tmp_dst;
    for (PII x : src_layer) {
      for (PII dir : src_dirs) {
        PII n = {x.FI+dir.FI,x.SE+dir.SE};
        if(n.FI<0||n.FI>=N)continue;
        if(n.SE<0||n.SE>=M)continue;
        if(grid[n.FI][n.SE]=='#')continue;
        if(src_dist[n.FI][n.SE]){
          continue;
        }
        src_dist[n.FI][n.SE]=1;
        if (dst_dist[n.FI][n.SE]){
          return l;
        }
        tmp_src.PB(n);
      }
    }
    for (PII x : dst_layer) {
      for (PII dir : dirs) {
        PII n = {x.FI+dir.FI,x.SE+dir.SE};
        if (n.FI < 0 || n.FI >= N) continue;
        if (n.SE < 0 || n.SE >= M) continue;
        if (grid[n.FI][n.SE] == '#') continue;
        if (dst_dist[n.FI][n.SE]) {
          continue;
        }
        dst_dist[n.FI][n.SE] = 1;
        if (src_dist[n.FI][n.SE]) {
          return l;
        }
        tmp_dst.PB(n);
      }
    }
    dst_layer=tmp_dst;
    CLR(tmp_dst);
    for (PII x : dst_layer) {
      for (PII dir : dirs) {
        PII n = {x.FI+dir.FI,x.SE+dir.SE};
        if (n.FI < 0 || n.FI >= N) continue;
        if (n.SE < 0 || n.SE >= M) continue;
        if (grid[n.FI][n.SE] == '#') continue;
        if (dst_dist[n.FI][n.SE]) {
          continue;
        }
        dst_dist[n.FI][n.SE] = 1;
        if (src_dist[n.FI][n.SE]) {
          return l;
        }
        tmp_dst.PB(n);
      }
    }
    src_layer=tmp_src;
    dst_layer=tmp_dst;
  }
  return -1;
}

int main(int argc, char* argv[]) {
  read(N,M);
  REP(i,N){
    REP(j,M){
      scanf(" %c",&grid[i][j]);
    }
  }
  int ans = doit();
  if (ans < 0) {
    printf("NO\n");
  } else {
    printf("YES\n");
    printint(ans);
  }
  return 0;
}