牛客小白月赛61-C-小喵觅食

很经典的bfs,就是从猫咪和MM的坐标开始bfs搜索

不过这题有些小细节需要注意

1.认真审题,注意,猫一旦闻到小鱼干的味道,开始动,此时MM就不动了,一开始没仔细审题,很不好的习惯

2.注意移动的条件,vis,不是墙,距离是MM的移动距离范围内

3.这个猫咪的r2是闻味道的r2,不是移动距离的r2,还是审题的问题

4.猫闻到味道,开始动,此时是一直bfs,直到到达MM的坐标,因此需要对MM停下的位置做个标记

这道题很经典,实现起来也需要注意些细节,非常好的一道题,很有练习意义

// Problem: 小喵觅食
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/46597/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Date: 2024-03-14 20:47:16
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define endl '\n'
#define int int64_t
using namespace std;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int r1, r2, xc, yc, xm, ym, n, m;
int dis(int xb, int yb, int xed, int yed) {return abs(xb - xed) + abs(yb - yed);
}
char ches[1003][1003];
int vis[1003][1003];
int vis_c[1003][1003];
int dm[1003][1003];
int dc[1003][1003];
bool smell = false;
int ans = INT_MAX;
void bfs_m(int x, int y) {queue<pair<int, int>>q;q.push({ x,y });vis[x][y] = 1;dm[x][y] = 0;if (dis(x, y, xc, yc) <= r2) {smell = true;vis[x][y] = 1e9;return;}while (q.size()) {int u = q.front().first;int v = q.front().second; q.pop();for (int i = 0; i < 4; ++i) {int nx = u + dx[i];int ny = v + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m)continue;if (!vis[nx][ny] && ches[nx][ny] != '*' && dis(x, y, nx, ny) <= r1) {q.push({ nx,ny });vis[nx][ny] = 1;dm[nx][ny] = dm[u][v] + 1;if (dis(nx, ny, xc, yc) <= r2) {smell = true;vis[x][y] = 1e9;return;}}}}
}
void bfs_c(int x, int y) {queue<pair<int, int>>q;q.push({ x,y });vis_c[x][y] = 1;dc[x][y] = 0;while (q.size()) {int u = q.front().first;int v = q.front().second; q.pop();for (int i = 0; i < 4; ++i) {int nx = u + dx[i];int ny = v + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m)continue;if (!vis_c[nx][ny] && ches[nx][ny] != '*') {q.push({ nx,ny });vis_c[nx][ny] = 1;dc[nx][ny] = dc[u][v] + 1;if (vis[nx][ny] == 1e9) {ans = min(ans, dc[nx][ny] + dm[nx][ny]);}}}}
}
void solve() {cin >> n >> m;cin >> r1 >> r2;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> ches[i][j];if (ches[i][j] == 'P')xm = i, ym = j;if (ches[i][j] == 'M')xc = i, yc = j;}}bfs_m(xm, ym);if (!smell) cout << -1 << endl;else {bfs_c(xc, yc);if (ans != INT_MAX)cout << ans << endl;elsecout << -1 << endl;}
}
signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t = 1;//cin >> t;while (t--) {solve();}return 0;
}