牛客小白月赛61-C-小喵觅食

题目描述 
The__Flash 回到家迫不及待地跟 PLMM 分享买回来的零食，PLMM 拿起一包小鱼干正准备要吃，这时恰巧有一只小喵在觅食，引起了 PLMM 的注意。
现实世界可以抽象为一张 n×m大小的二维地图。PLMM 的初始坐标在(x1​,y1​)，活动范围 r1表示 PLMM 只会移动到坐标为 (x,y)的位置 (0≤∣x−x1∣+∣y−y1∣≤r1)。小喵的初始坐标在 (x2,y2)，鼻子灵敏度 r2 表示小喵只能闻到坐标为 (x,y)的位置的小鱼干 (0≤∣x−x2∣+∣y−y2∣≤r2)。此外，地图中存在若干障碍物使得 PLMM 和小喵无法通过。

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

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

输入描述 
一行输入两个整数 n,m (1≤n,m≤103)。第二行输入两个整数 r1,r2 (1≤r1,r2≤max(n,m))。
接下来输入 n行，每行输入一个长度为 m 的字符串 s[i]表示二维地图。s[i][j] (s[i][j]∈{′P′,′M′,′∗′,′.′})表示地图坐标为 (i,j) (1≤i≤n,1≤j≤m)的位置，其中 ′P′表示 PLMM 的初始位置，′M′ 表示小喵的初始位置，′∗′ 表示障碍物不允许通过，′.′ 表示空地允许通过。
保证地图中字符 ′P′ 有且仅有一个，字符 ′M′有且仅有一个。

输出描述 

若小喵可以吃到小鱼干则输出 PLMM 与小喵移动的距离和最小值，否则输出 -1。

输入：

5 3
2 1
...
.M.
...
...
.P.

输出：

3

解析：我们可以直接看成两种情况，一种是人行走范围内，猫都闻不到，输出-1，另一种是人行走范围内，猫能闻到，此时我们可以直接看成人一步都不走，猫为起点，人为终点，然后求起点到终点的最短路径，因为此时两者相加最短跟人不动，猫动求得答案等价。

1.可以用dfs来判断人行走的所有范围，如果某个点，猫能闻到，那么flag为true即可，如果所有能到的点都闻不到就是-1的情况

2.有解情况，利用bfs来求得最短路即可

#include 
#include 
#include 
using namespace std;
const int N=1005;
int dist[N][N],n,m,qx,qy,zx,zy,r1,r2;
bool st[N][N];
char a[N][N];//保存地图 
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
typedef pair<int,int> PII;
void bfs()//求起点到终点的最短路径 
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) dist[i][j]=0x3f3f3f3f;
	}
	queue q;
	q.push({qx,qy});
	dist[qx][qy]=0;
	st[qx][qy]=true;
	while(q.size())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int x3=x+dx[i];
			int y3=y+dy[i];
			if(!(x3>=1&&x3<=n&&y3>=1&&y3<=m)) continue;
			if(a[x3][y3]=='*') continue;
			if(!st[x3][y3])
			{
				dist[x3][y3]=dist[x][y]+1;
				q.push({x3,y3});
				st[x3][y3]=true;
			}
		}
	}	
}
bool flag;//记录能否让猫闻到 
bool st1[N][N];//记录点是否已经走过 
void dfs(int x,int y)//遍历人能到的所有点 
{
	if((abs(x-zx)+abs(zy-y))>r1||flag||st1[x][y]==true) return; 
	st1[x][y]=true;
	for(int i=0;i<4;i++)
	{
		int x3=x+dx[i];
		int y3=y+dy[i];
		if(!(x3>=1&&x3<=n&&y3>=1&&y3<=m)) continue;
		if(a[x3][y3]=='*'||st1[x3][y3]) continue;
		if((abs(x-qx)+abs(qy-y))<=r2)
		{
			flag=true;
			break;
		}
		dfs(x3,y3);
	}
}
void solve()
{
	flag=false;
	dfs(zx,zy);
	if(!flag)//如果人行走范围都无法让猫闻到 
	{
		printf("-1\n");
		return;
	}
	bfs();
	if(dist[zx][zy]==0x3f3f3f3f) printf("-1\n");//表示到不了
	else printf("%d\n",dist[zx][zy]);
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&r1,&r2);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf(" %c",&a[i][j]);
			if(a[i][j]=='P') zx=i,zy=j,a[i][j]='.';//记录终点，并变为'.'表示可走 
			if(a[i][j]=='M') qx=i,qy=j;//记录起点 
		}
	}
	solve();
	return 0;
}