牛客小白月赛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;
		else
			cout << -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;
}