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

题目

格式

样例

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

3

PLMM 进行移动 $(5,2)\to (4,2)\to (3,2)(5,2)\to (4,2)\to (3,2)(5,2)\backslash rightarrow(4,2)\backslash rightarrow(3,2)(5,2)\to (4,2)\to (3,2)$，此时小喵闻到了坐标 $(3,2)(3,2)(3,2)(3,2)$ 位置上小鱼干的气味并进行移动 $(2,2)\to (3,2)(2,2)\to (3,2)(2,2)\backslash rightarrow(3,2)(2,2)\to (3,2)$。

思路

假设有通路, 那么从人和猫汇合可以看做人一口气走到了猫的地方

那么我们只需要预处理出人走到每个点的步数 + 那些点可以满足通路的条件 即可 对于前半部分，因为 $1\le n,m\le 10^{3}1\le n,m\le 10^3$ ，所以我们可以选择比较简单朴素的 bfs

const int N = 1010 + 12;
int n, m, r1, r2;
char g[N][N];
int d[N][N];
bool st[N][N];
int sx, sy, ex, ey; // 起点终点
queue<pii> que;

void bfs()
{
	que.push({sx, sy});
	d[sx][sy] = 1;
	
	while (que.size())
	{
		pii it = que.front(); que.pop();
		
		for (int i=0;i < 4;i ++ )
		{
			int a = it.fr + dx[i].fr;
			int b = it.sc + dx[i].sc;
			if (1 <= a && a <= n && 1 <= b && b <= m)
			{
				if (st[a][b] || g[a][b] == '*') continue ;
				
				d[a][b] = d[it.fr][it.sc] + 1;
				st[a][b] = 1;
				que.push({a, b});
			}
		}
	}
}

根据第二个满足通路的条件, 我们直接枚举矩阵所有的点，如果这个点到猫的距离小于等于 $r2r2$ 时，并且这个点我们花费 $r1r1$ 可以走到，那么当前满足通路，我们直接输出 $d[ex][ey]d[ex][ey]$ 即可

const int N = 0x3f3f3f3f;

inline int len(int a, int b)
{
	return abs(a-ex) + abs(b-ey);
}

int mi = Inf;
for (int i=1;i <= n;i ++ )
{
	for (int j=1;j <= m;j ++ )
	{
		if (len(i,j) <= r2 && d[i][j] && d[i][j] <= r1+1)
			return cout<<d[ex][ey]-1, 0;
	}
}

代码

#include <iostream>
#include <queue>
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 1010, Inf = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, m, r1, r2;
char g[N][N];
int d[N][N];
bool st[N][N];
int sx, sy, ex, ey;
queue<pii> que;

inline int len(int a, int b)
{
	return abs(a-ex) + abs(b-ey);
}

pii dx[] = {
	{0, 1}, {0, -1}, {1, 0}, {-1, 0}
};

void bfs()
{	// bfs 模板
	que.push({sx, sy});
	d[sx][sy] = 1;
	
	while (que.size())
	{
		pii it = que.front(); que.pop();
		
		for (int i=0;i < 4;i ++ )
		{
			int a = it.fr + dx[i].fr;
			int b = it.sc + dx[i].sc;
			if (1 <= a && a <= n && 1 <= b && b <= m)
			{
				if (st[a][b] || g[a][b] == '*') continue ;
				
				d[a][b] = d[it.fr][it.sc] + 1;
				st[a][b] = 1;
				que.push({a, b});
			}
		}
	}
}

signed main()
{
	cin >> n >> m >> r1 >> r2;
	for (int i=1;i <= n;i ++ )
		for (int j=1;j <= m;j ++ ) // 下标从1开始
		{
			cin >> g[i][j];
			if (g[i][j] == 'P') sx=i, sy=j; // 记录起点和终点
			else if (g[i][j] == 'M') ex=i, ey=j;
 		}
 	
 	bfs();
	
	int mi = Inf;
	for (int i=1;i <= n;i ++ )
	{		// 直接暴力枚举
		for (int j=1;j <= m;j ++ )
		{	// 是否闻得到			是否能走	是否走的到
			if (len(i,j) <= r2 && d[i][j] && d[i][j] <= r1+1)
				return cout<<d[ex][ey]-1, 0;
		}
	}
	// 如果没有 return 就是非法 输出-1
	cout << -1;
	
	return 0;
}