Codeforces 198 B Jumping on Walls

题面翻译

题目描述

瓦西亚在和忍者玩电脑游戏。在这个关卡，瓦西亚需要操控忍者走出一个很深的峡谷。

峡谷由两面垂直于地面且互相平行的墙组成，它们的高度为\(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\)开始。

这可能是我有史以来写的最认真的一篇博客