小喵觅食

The__Flash 回到家迫不及待地跟 PLMM 分享买回来的零食，PLMM 拿起一包小鱼干正准备要吃，这时恰巧有一只小喵在觅食，引起了 PLMM 的注意。

现实世界可以抽象为一张 $n \times m$ 大小的二维地图。PLMM 的初始坐标在 $(x_1,y_1)$ ，活动范围 $r_1$ 表示 PLMM 只会移动到坐标为 $(x,y)$ 的位置 $(0 \leq |x-x_1|+|y-y_1| \leq r_1)$ 。小喵的初始坐标在 $(x_2,y_2)$ ，鼻子灵敏度 $r_2$ 表示小喵只能闻到坐标为 $(x,y)$ 的位置的小鱼干 $(0 \leq |x-x_2|+|y-y_2| \leq r_2)$ 。此外，地图中存在若干障碍物使得 PLMM 和小喵无法通过。

若 PLMM 或小喵当前的坐标为 $(x,y)$ ，则下一步可以移动到 $(x-1,y),\,(x,y-1),\,(x+1,y)$ 或 $(x,y+1)$ 坐标的位置。起初，小喵保持原地不动，但当闻到小鱼干的气味时便会朝 PLMM 的位置跑去。在小喵开始移动的同时，PLMM 会担心吓跑小喵从而保持原地不动。需要注意的是，鼻子灵敏度 $r_2$ 只能决定小喵能否闻到小鱼干的气味，对小喵的移动范围没有限制。小喵闻到小鱼干气味后便会锁定 PLMM 的位置，即使之后闻不到小鱼干的位置，也会继续朝 PLMM 的位置移动。

若小喵可以吃到小鱼干，PLMM 想知道自己与小喵移动的距离和最小值。

第一行输入两个整数 $n,m\,(1 \leq n,m \leq 10^3)$ 。

第二行输入两个整数 $r_1,r_2 \, (1 \leq r1,r2 \leq max(n,m))$ 。

接下来输入 $n$ 行，每行输入一个长度为 $m$ 的字符串 $s[i]$ 表示二维地图。 $s[i][j]\,(s[i][j] \in \{'P','M','*','.'\})$ 表示地图坐标为 $(i,j)\,(1 \leq i \leq n, 1 \leq j \leq m)$ 的位置，其中 $'P'$ 表示 PLMM 的初始位置， $'M'$ 表示小喵的初始位置， $'*'$ 表示障碍物不允许通过， $'.'$ 表示空地允许通过。

保证地图中字符 $'P'$ 有且仅有一个，字符 $'M'$ 有且仅有一个。

#include<bits/stdc++.h> using namespace std; char mp[1005][1005]; bool vis[1005][1005]; int go[4][2] = {0,1,1,0,0,-1,-1,0}; struct Point{ int x,y,len; }; int a,b,c,d,i,j,k,r1,r2,n,m; int bfs(){ queue<Point> q; q.push({a,b,0}); vis[a][b] = 1; int len = 0; while(!q.empty()){ Point t; t = q.front();q.pop(); len = t.len; if(t.len <= r1 && abs(t.x - c) + abs(t.y - d) <= r2)k = 1; if(k == 1 && mp[t.x][t.y] == 'M')return len; for(int i = 0;i < 4;i++){ int xx = t.x + go[i][0]; int yy = t.y + go[i][1]; if(xx < 1 || xx > n || yy < 1|| yy > m||vis[xx][yy] == 1|| mp[xx][yy] == '*')continue; vis[xx][yy] = 1; q.push({xx,yy,len + 1}); } } return 0; } int main(){ cin>>n>>m>>r1>>r2; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin>>mp[i][j]; if(mp[i][j] == 'P')a = i,b = j; if(mp[i][j] == 'M')c = i,d = j; } } int e = bfs(); if(!e)cout<<"-1"; else cout<<e; }

详情