Description

在n*m的图上有两个人 一个人可以走八连通一次只能走一步 另一个人可以走四连通能走两步 问最短相遇时间

Solution

考虑bfs n和m也不大 分别用不同的vis来标记他们走过的路 当一个人走下一步得时候看对方是否已经走过 对于这种需要走多步的 往往都是直接bfs的次数 = 步数 分别用两个队列去模拟就好了 复杂度O(n*m)

Code

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x, a) memset(x, a, sizeof(x));
#define sca(a) scanf("%d", &a)
#define lowbit(x) x&(-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

const int N = 1005;

char mp[N][N];
bool visx[N][N], visy[N][N];

int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};

struct node {
  int x, y;
};

int n, m;

node s, t;

bool check(int x, int y) {
  if (x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != '#') {
    return 1;
  }
  return 0;
}

queue<node> q[2];

bool bfs(int id) {
  int size = q[id].size();

  while (size --) {//注意不是判断队列非空 size--代表就当前这一步的拓展
    node now = q[id].front();
    q[id].pop();

    int x, y;

    for (int i = 0; i < 8 - 4 * id; i++) {
      x = now.x + dx[i];
      y = now.y + dy[i];

      if (id == 0) {
        if (check(x, y)) {//判断是否能走后 直接看是否已经走过
          if(visy[x][y]){
              return 1;
          }
          node next;
          next.x = x;
          next.y = y;

          if(!visx[x][y]){
              visx[x][y] = 1;
              q[id].push(next);
          }
        }
      } else {
        if (check(x, y)) {
          if(visx[x][y]){
              return 1;
          }
          node next;
          next.x = x;
          next.y = y;

          if(!visy[x][y]){
              visy[x][y] = 1;
              q[id].push(next);
          }
        }
      }
    }
  }
  return 0;
}

int solve() {
  int res = 0;

  while (!q[0].empty() || !q[1].empty()) {
    res++;

    if (bfs(0)) return res;
    if (bfs(1)) return res;
    if (bfs(1)) return res;
  }

  return -1;
}

int main() {
  ios::sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> mp[i][j];
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (mp[i][j] == 'C') {
        s.x = i;
        s.y = j;
        visx[i][j] = 1;
      }

      if (mp[i][j] == 'D') {
        t.x = i;
        t.y = j;
        visy[i][j] = 1;
      }
    }
  }

  q[0].push(s);
  q[1].push(t);

  int res = solve();

  if (res == -1) {
    cout << "NO" << '\n';
  } else {
    cout << "YES" << '\n';
    cout << res << '\n';
  }
  return 0;
}