小A与小B 搜索

题意：就是一个人走八个方向，每次走一步，一个人走四个方向，每次走2步，问最少基几步两个人相遇。
题解：首先我们要考虑好走两步的如何走，我们不能简单的把他弄成每一次直接就走2步，比如，...#D，这样子的话如果你走2步他直接就跳过障碍物了，但是实际上是走不通的，我们就可以把他处理一下，把两部变成走两次不就好啦，进行2次bfs，然后就可以解决啦，然后再同时进行另一个人的BFS，那么我们就判断他们在哪儿相遇就好啦。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,1,0,-1,-1,1,1,-1};
   int n,m;
struct node
{
    int x,y;
}q;
queue<node>ss[2];
bool flag;
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
char ans[1010][1010];
int vis[1010][1010][2];
bool bfs(int a)
{
  int s=ss[a].size();
  while(s--)
  {
      node p=ss[a].front();
      ss[a].pop();
      for(int i=0;i<4+(a?0:4);i++)
      {
          int xx=p.x+dx[i];
          int yy=p.y+dy[i];
          if(xx<1||xx>n||yy<1||yy>m||ans[xx][yy]=='#'||vis[xx][yy][a]) continue;
          if(vis[xx][yy][!a]) return flag=true;
          vis[xx][yy][a]=1;
          node e;
          e=node{xx,yy};
          ss[a].push(e);
      }
  }
   return flag=false;
}
int main()
{
    int xa,ya,xb,yb;
   cin>>n>>m;
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m;j++)
         {
             cin>>ans[i][j];
             if(ans[i][j]=='C')
                xa=i,ya=j;
                if(ans[i][j]=='D')
                    xb=i,yb=j;
         }
     }
    // cout<<xa<<" "<<ya<<endl;
     q=node{xa,ya},ss[0].push(q);
     q=node{xb,yb},ss[1].push(q);
     int sum=0;
     while(ss[0].size()||ss[1].size())
     {
         sum++;
         if(bfs(1)) break;
         if(bfs(1)) break;
         if(bfs(0)) break;
     }
     if(flag)
        cout<<"YES"<<"\n"<<sum<<endl;
     else
        puts("NO");
    return 0;
}