题面翻译
题目描述
瓦西亚在和忍者玩电脑游戏。在这个关卡，瓦西亚需要操控忍者走出一个很深的峡谷。
峡谷由两面垂直于地面且互相平行的墙组成，它们的高度为\(n\)米。我们将这些墙分成许多\(1\)米长的区域，并从下到上用\(1\)到\(n\)的正整数对它们进行编号。有些地方是安全的，忍者可以爬上去。有些地方石头很尖锐，忍者不能待在那里。我们称这些地区为危险地区。
最初忍者在左墙的最下方。他每秒可以执行以下操作之一：
-
向上爬一个区域；
-
向下爬一个区域；
-
跳到对面的墙上。忍者会跳到比他当前所在高度高\(k\)米的地方。更准确地说，如果在跳跃之前忍者位于一面墙的区域\(x\)，那么在跳跃之后，他位于另一面墙的区域\(x + k\)。
如果在某个时间点忍者到达了一个高度大于\(n\)的区域，那么忍者就可以从峡谷中出来了。
但峡谷被水淹没了，每秒水位会上升一米。最初，水位达到区域\(1\)的下边界。忍者不能待在被水淹没的地方。忍者和水轮流移动——首先忍者行动，然后水上升一米，然后忍者再行动，以此类推。
如果忍者可以离开峡谷，那这个关卡就完成了。
在几次失败的尝试之后，瓦西亚开始怀疑是否有可能完成这一关卡。请回答他的问题。
输入输出格式
输入格式：
第一行包含两个整数\(n\)和\(k\) \((1 \leq n ,k \leq 10^5)\)——峡谷的高度和忍者可以跳跃的高度
第二行包含左墙的描述——一个长度为\(n\)个字符的字符串。第\(i\)个字符表示墙的区域\(i\)的状态：字符“X”表示危险区域，“-”表示安全区域。
第三行以相同的格式描述了右墙。
数据保证左墙的第一个区域不是危险区域。
输出格式：
如果忍者能从峡谷中出来，打印“YES”（不带引号），否则，打印“NO”（不带引号）。
样例 #1
样例输入 #1
7 3
---X--X
-X--XX-
样例输出 #1
YES
样例 #2
样例输入 #2
6 2
--X-X-
X--XX-
样例输出 #2
NO
说明
在第一个样例中，忍者可以先跳到右边的墙，然后沿着右边的墙往下走一米，然后跳到左边的墙。再跳跃一次忍者就可以离开峡谷。
在第二个样例中，忍者是无法离开峡谷的。
思路
\(BFS\) 基础练习题
上来就是\(BFS\)四部曲：初始化、更新、出口和转移。
这里我们用到了tuple元组（就是pair<pair<int,int> ,int >，但这个pair套pair应该没人用了）作为队列的元素。
元组中三个元素分别表示忍者的高度，左右哪面墙上和时间（水的高度）。
出口有两个，分别是被水淹没和逃出峡谷。
转移有三个，分别对应题目中所描述的三个移动方式。
代码实现
#include<bits/stdc++.h>
using namespace std;
int d[100005][2];
char s[2][100005];
queue<tuple<int,int,int> > q;
int main()
{
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
cin>>s[0];cin>>s[1];
//初始化bfs
for(int i=1;i<=n;i++)
{
if(s[0][i-1]=='X')
d[i][0]=1;
if(s[1][i-1]=='X')
d[i][1]=1;
}
tuple<int,int,int> tp{1,0,0};
q.push(tp);
while(!q.empty())
{
//更新bfs
tuple<int,int,int> tp=q.front();
int x=get<0>(tp),y=get<1>(tp),t=get<2>(tp);
q.pop();
//出口
if(x>n)
{
cout<<"YES"<<endl;
return 0;
}
if(x<=t||d[x][y]==1)
continue;
//转移
d[x][y]=1;
tuple<int,int,int> t1{x-1,y,t+1},t2{x+1,y,t+1},t3{x+k,1-y,t+1};
q.push(t1),q.push(t2),q.push(t3);
}
cout<<"NO"<<endl;
return 0;
}
注意
在初始化\(BFS\)时要特别注意，d数组的行坐标是从\(1\)开始的，所以for循环也要从\(1\)开始。
这可能是我有史以来写的最认真的一篇博客