网站开发进入腾信职位,安卓app开发工具,一站式网站建设服务商,专业制作小程序的公司很经典的bfs,就是从猫咪和MM的坐标开始bfs搜索
不过这题有些小细节需要注意
1.认真审题,注意,猫一旦闻到小鱼干的味道,开始动,此时MM就不动了,一开始没仔细审题,很不好的习惯
2.注意移动的条件,vis,不是墙,距离是MM的移动距离范围内
3.这个猫咪的r2是闻味道的r2,不是移动距…很经典的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)#includebits/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) {queuepairint, intq;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) {queuepairint, intq;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;
}
