荷香堪筑梦，鸳鸯和月寻。（变相BFS搜索）

原创于 2024-05-07 20:16:54 发布 · 粉丝可见 · 393 阅读 · 1 · 5 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/138543744

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

`cobol<br/>3 4 2<br/>....<br/>***.<br/>..a.<br/>`

yes

思路：

根据题意，这里 1 s 可以移动多次，我们将每次可以移动避开雪的的位置存储起来，判断当移动到了顶部，说明完全可以避开雪。

代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();

signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
	// cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
int n,m,k;
char g[1010][1010];		// 下雪图
bool st[1010][1010];	// 标记是否走过
using PII = pair<int,int>;
inline void BFS(int x,int y)
{
	queue<PII>q;
	q.emplace(x,y);
	st[x][y] = true;
	while(q.size())
	{
		PII now = q.front();
		q.pop();
		
		// 如果到达了最顶部，说明完全避开了所以雪
		if(now.x == 1)
		{
			cout << "yes" << endl;
			return ;
		}
		
		st[now.x][now.y] = true;
		
		// 当前位置 的 上右边可移动最长距离
		int rlen = min(now.y + k,m);
		
		for(int i = now.y;i <= rlen;++i)
		{
			// 如果这个位置没走过，我们存储起来可以走到这个的位置
			if(g[now.x - 1][i] == '.' and !st[now.x - 1][i])
			{
				// 标记这里走过了
				st[now.x - 1][i] = true;
				q.emplace(PII(now.x - 1,i));
			}
		}
		// 当前位置 的 上右边可移动最长距离
		int llen = min(now.y - k,1LL);
		
		for(int i = now.y - 1;i >= llen;--i)
		{
			// 如果这个位置没走过，我们存储起来可以走到这个的位置
			if(g[now.x - 1][i] == '.' and !st[now.x - 1][i])
			{
				// 标记这里走过了
				st[now.x - 1][i] = true;
				q.emplace(PII(now.x - 1,i));
			}
		}
	}
	cout << "no" << endl;	// 如果一直走不到 顶部，输出no
}
inline void solve()
{
	int x,y;
	cin >> n >> m >> k;
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= m;++j)
		{
			cin >> g[i][j];
			if(g[i][j] == 'a')
			{
				x = i;
				y = j;
			}
		}
	}
	
	BFS(x,y);
}