题意
给定一个迷宫,迷宫中 A 可以向 8 个方向移动(八联通的 8 个方向),B 可以向 4 个方向移动(四联通的 4 个方向),但一单位时间可以移动两次。不能通过障碍物。问 A 和 B 是否能相遇、最早什么时候相遇。
题解
一开始理解错意思了,以为相遇必须是在某一时刻到达同一个格子。于是开始纠结 B 的“走两步”算一个还是半个时刻。
后来发现想多了,只要 A 和 B 都到达过某个格子就行了。那么直接上双向 BFS 即可。
#include <bits/stdc++.h> #define INF 2000000000 #define MOD 1000000007 #define MAXN 200005 #define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp) #define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> intpair; int read(){ int f = 1, x = 0; char c = getchar(); while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } inline int lowbit(int x){ return x & (-x); } inline int modadd(int x, int y){ return (x + y >= MOD ? x + y - MOD: x + y); } inline int sgn(int x){ return (x < 0 ? -1: (x > 0 ? 1: 0)); } template<typename T> T gcd(T a, T b){ return (!b) ? a: gcd(b, a % b); } const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1}; const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; /*--------------------------------------------------------------------*/ /*--------------------------------------------------------------------*/ int n, m; int ax, ay, bx, by; char o[3], mat[1005][1005]; queue<int> qx1, qx2, qy1, qy2; bool vis1[1005][1005] = {0}, vis2[1005][1005]; void init(){ n = read(), m = read(); for (int i = 1; i <= n; ++i){ for (int j = 1; j <= m; ++j){ scanf("%s", o); mat[i][j] = o[0]; if (o[0] == 'C') ax = i, ay = j; if (o[0] == 'D') bx = i, by = j; } } } bool stepa(){ int siz1 = qx1.size(); while (siz1--){ int x = qx1.front(), y = qy1.front(); qx1.pop(), qy1.pop(); for (int i = 0; i < 8; ++i){ int cx = x + ddx[i], cy = y + ddy[i]; if (cx <= 0 || cy <= 0 || cx > n || cy > m) continue; if (mat[cx][cy] == '#' || vis1[cx][cy]) continue; vis1[cx][cy] = true; if (vis2[cx][cy]) return true; qx1.push(cx), qy1.push(cy); } } return false; } bool stepb(){ int siz2 = qx2.size(); while (siz2--){ int x = qx2.front(), y = qy2.front(); qx2.pop(), qy2.pop(); for (int i = 0; i < 4; ++i){ int cx = x + dx[i], cy = y + dy[i]; if (cx <= 0 || cy <= 0 || cx > n || cy > m) continue; if (mat[cx][cy] == '#' || vis2[cx][cy]) continue; vis2[cx][cy] = true; if (vis1[cx][cy]) return true; qx2.push(cx), qy2.push(cy); } } return false; } bool step(){ if (stepa()) return true; if (stepb()) return true; if (stepb()) return true; return false; } void solve(){ vis1[ax][ay] = true; vis2[bx][by] = true; qx1.push(ax), qy1.push(ay); qx2.push(bx), qy2.push(by); int ans = 0x3f3f3f3f; for (int st = 1; ; ++st){ if (qx1.empty() && qx2.empty()){ printf("NO\n"); return ; } if (step()){ printf("YES\n%d\n", st); return ; } } } int main(){ init(); solve(); return 0; }