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; }