错误版本

本题可以理解为矩阵上的单源最短路径，因为数据不是很大，我们可以使用BFS进行搜索PLMM和猫到达图中所有点的最短路径。但是题目加上了附属条件，PLMM走的步数是有限的，而且猫的嗅觉也是有限的。所以我们可以求完最短路径之后，找到一个可以同时满足两个要求的点，如果可以找到，则更新答案。不能则输出-1。
bug样例：
5 3
1 2
P..
.*.
*..
M..
...
(感谢大佬补充数据）

#include <bits/stdc++.h>
using namespace std;
int n, m;
int r, l;
bool vis[2000][2000];
int ans = 0;
char mp[2000][2000];
int sum[2000][2000];
int dp[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
struct pii
{
    int x, y;
} s, e;
void bfs()
{
    sum[s.x][s.y] = 0;
    queue<pii> p;
    p.push(s);
    while (p.size())
    {
        pii q = p.front();
        p.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = q.x + dp[i][0], y = q.y + dp[i][1];
            if (x < 0 || y < 0 || x >= n || y >= m)
                continue;
            if (mp[x][y] == '*')
                continue;
            sum[x][y] = min(sum[x][y], sum[q.x][q.y] + 1);
            if (!vis[x][y])
            {
                vis[x][y] = true;
                p.push({x, y});
            }
        }
    }
}
int main(void)
{
    cin >> n >> m;
    cin >> l >> r;
    memset(sum, 0x3f, sizeof sum);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mp[i][j];
    //寻找起始点和终点
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 'M')
                e.x = i, e.y = j;
            if (mp[i][j] == 'P')
                s.x = i, s.y = j;
        }
    //求最短路径
    bfs();
    int flag = 0;
    if (sum[e.x][e.y] >= 0x3f3f3f3f)
    {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (sum[i][j] < 0x3f3f3f3f)
            {
                //寻找满足r1,r2的要求的点
                int ll = sum[i][j];
                int rr = abs(i - e.x) + abs(j - e.y);
                if (ll <= l && rr <= r)
                {
                    cout << sum[e.x][e.y] << endl;
                    return 0;
                }
            }
    }
    cout << -1 << endl;
}

正确版本

将上面的代码在bfs一遍小猫的路径，然后将满足条件的点当做中转站，不断更新答案就可以
ans = min(ans, sum[i][j] + sum1[i][j]);
AC代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int r, l;
bool vis[2000][2000];
int ans = 0;
char mp[2000][2000];
int sum[2000][2000];
int dp[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
struct pii
{
    int x, y;
} s, e;
void bfs()
{
    sum[s.x][s.y] = 0;
    queue<pii> p;
    p.push(s);
    while (p.size())
    {
        pii q = p.front();
        p.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = q.x + dp[i][0], y = q.y + dp[i][1];
            if (x < 0 || y < 0 || x >= n || y >= m)
                continue;
            if (mp[x][y] == '*')
                continue;
            sum[x][y] = min(sum[x][y], sum[q.x][q.y] + 1);
            if (!vis[x][y])
            {
                vis[x][y] = true;
                p.push({x, y});
            }
        }
    }
}
int sum1[2000][2000];
void bfs1()
{
    sum1[e.x][e.y] = 0;
    queue<pii> p;
    p.push(e);
    while (p.size())
    {
        pii q = p.front();
        p.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = q.x + dp[i][0], y = q.y + dp[i][1];
            if (x < 0 || y < 0 || x >= n || y >= m)
                continue;
            if (mp[x][y] == '*')
                continue;
            sum1[x][y] = min(sum1[x][y], sum1[q.x][q.y] + 1);
            if (!vis[x][y])
            {
                vis[x][y] = true;
                p.push({x, y});
            }
        }
    }
}
int main(void)
{
    cin >> n >> m;
    cin >> l >> r;
    memset(sum, 0x3f, sizeof sum);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mp[i][j];
    //寻找起始点和终点
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 'M')
                e.x = i, e.y = j;
            if (mp[i][j] == 'P')
                s.x = i, s.y = j;
        }
    //求最短路径
    //PLMM到图中的最短路
    bfs();
    memset(sum1, 0x3f, sizeof sum1);
    memset(vis, 0, sizeof vis);
    //猫到图中的最短路
    bfs1();
    int flag = 0;
    if (sum[e.x][e.y] >= 0x3f3f3f3f)
    {
        cout << -1 << endl;
        return 0;
    }
    ans = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (sum[i][j] <= 0x3f3f3f3f)
            {
                //寻找满足r1,r2的要求的点
                int ll = sum[i][j];
                int rr = abs(i - e.x) + abs(j - e.y);
                if (ll <= l && rr <= r)
                //答案更新
                    ans = min(ans, sum[i][j] + sum1[i][j]);
            }
    }
    if (ans >= 0x3f3f3f3f)
        cout << -1 << endl;
    else
        cout << ans << endl;
}