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

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

题目：

样例：

输入

3 4 2 .... ***. ..a.

输出

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);
}

最后提交：