题解 | #小喵觅食(BFS)#

题意：给定二维字符矩阵，‘*’ 代表障碍且不能通过，‘.’代表空且可以通过，一人位于点(x1,y1)，一猫位于点(x2,y2)，当人走到与猫的曼哈顿距离小于r2时人停止走动，此时猫会向人走来。人的活动范围为r1，代表人不能走到与(x1,y1)曼哈顿距离大于r1的点上，注意：当且仅当人走到与(x2，y2)曼哈顿距离小于r2时猫才会向人走来，否则猫处于静止态。请你求出人想与猫汇合的话，人与猫走的步数之和最小是多少。如果无法汇合，请输出-1

思路：

首先，猫的移动范围不受限制，以猫为源点做全局的最短路（BFS）。将猫为源点的最短路记录在mp中

而后以人为源点，在r1和r2的限制条件下BFS出人能到的所有点并且标记出到这些点的最小步数。将人为源点的最短路记录在mp2中

值得注意的是，mp1和mp2初始化为无穷大，以便判断无解的情况。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long 
const int N =1000+100;
int n,m;
char a[N][N];
bool vis[N][N];
int mp[N][N][2];
int r1,r2;
int dir[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
int sx,sy,ex,ey;
struct node
{
    int x,y,dis;
};
bool check(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&a[x][y]!='*')
        return true;
    return false;
}
void BFS(int xx,int yy,int falg)
{
    queue<node> q;
    q.push({xx,yy,0});
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(a[now.x][now.y]!='*')
            mp[now.x][now.y][falg]=min(mp[now.x][now.y][falg],now.dis);
        if(vis[now.x][now.y]) continue;
        vis[now.x][now.y]=1;
        if(falg==1&&abs(now.x-sx)+abs(now.y-sy)<=r2) continue;
        for(int i=1;i<=4;i++)
        {
            node nex={now.x+dir[i][0],now.y+dir[i][1],now.dis+1};
            if(check(nex.x,nex.y))
            {
                if(falg==1)
                {
                    if(abs(nex.x-ex)+abs(nex.y-ey)<=r1)
                        q.push(nex);
                }
                else
                    q.push(nex);
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>r1>>r2;
    memset(mp,1e9,sizeof(mp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            mp[i][j][0]=1e9;mp[i][j][1]=1e9;
            if(a[i][j]=='M')
                sx=i,sy=j;
            if(a[i][j]=='P')
                ex=i,ey=j;
        }
    }
    BFS(sx,sy,0);
    memset(vis,0,sizeof(vis));
    BFS(ex,ey,1);
    int minn=1e9;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(abs(i-sx)+abs(j-sy)>r2||a[i][j]=='*') continue;
            else minn=min(minn,mp[i][j][0]+mp[i][j][1]);
    if(minn==1e9) cout<<-1;
    else cout<<minn;
    return 0;
}