Description

小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出“NO”。

Solution

这类问题通常都是用bfs做的，然后这道题比较特别的是小B可以连续移动两次，我们要考虑多种情况，一开始想的是走16(4 * 4)种情况，但是其实如果有障碍物的话，不能直接这样想，干脆让小B连续走两次，然后再更新他的step。这样的话就不会出现上面有障碍物的时候向上走两步的非法情况。基于这个思想，我们标记小A和小B走过的地方，如果小B走到小A走过的/小A走到小B走过的地方，那么就直接输出当前时间。然后注意不要出现越界情况，对于当前的x，y一定要先判断大小。

#include<bits/stdc++.h>

using namespace std;

bool vis1[1005][1005], vis2[1005][1005];
char maze[1005][1005];
int sx1, sy1, sx2, sy2;
int ans;
struct node {
  int x, y, step;
  node(int _x = 0, int _y = 0, int _step = 0): x(_x), y(_y), step(_step){}
};
int n, m;
int dist[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};
int p[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int bfs() {
  queue<node> q1, q2;
  q1.push(node(sx1, sy1, 0)), q2.push(node(sx2, sy2, 0));
  int x = 0;
  while(!q1.empty() || !q2.empty()) {
    ans++;
    int cur = q1.size();
    while(cur--) {
      node now = q1.front();
      q1.pop();
      for(int i = 0; i < 8; i++) {
        int xx = now.x + dist[i][0];
        int yy = now.y + dist[i][1];
        if(vis2[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1) return ans;
        if(!vis1[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1 && maze[xx][yy] == '.') {
          vis1[xx][yy] = 1;
          q1.push(node(xx, yy, now.step + 1));
        }
      }
    }
    cur = q2.size();
    int cur2 = cur;
    while(q2.size() && cur2--) {
      node now = q2.front();
      q2.pop();
      for(int i = 0; i < 4; i++) {
        int xx = now.x + p[i][0];
        int yy = now.y + p[i][1];
        if(vis1[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1) return ans;
        if(!vis2[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1 && maze[xx][yy] == '.') {
          vis2[xx][yy] = 1;
          q2.push(node(xx, yy, now.step));
        }
      }
    }
    while(q2.size() && cur--) {
      node now = q2.front();
      q2.pop();
      for(int i = 0; i < 4; i++) {
        int xx = now.x + p[i][0];
        int yy = now.y + p[i][1];
        if(vis1[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1) return ans;
        if(!vis2[xx][yy] && xx <= n && yy <= m && xx >= 1 && yy >= 1 && maze[xx][yy] == '.') {
          vis2[xx][yy] = 1;
          q2.push(node(xx, yy, now.step + 1));
        }
      }
    }    
  }
  return -1;
}
int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> maze[i][j];
      if(maze[i][j] == 'D') {
        sx2 = i, sy2 = j;
        vis2[sx2][sy2] = 1;
      }
      if(maze[i][j] == 'C') {
        sx1 = i, sy1 = j;
        vis1[sx1][sy1] = 1;
      }
    }
  }
  //cout << sx1 << ' ' << sx2 << ' ' << sy1 << ' ' << sy2 << "\n";
  if(bfs() == -1) {
    cout << "NO\n";
  } else {
    cout << "YES\n";
    cout << ans << "\n";
  }
  return 0;
}