Kenken Race

2024-01-24 13:58

文章标签 race kenken

本文主要是介绍Kenken Race，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Kenken Race

题目描述：
There are N squares arranged in a row, numbered 1,2,…,N from left to right. You are given a string S of length N consisting of . and #. If the i-th character of S is #, Square i contains a rock; if the i-th character of S is ., Square i is empty.
In the beginning, Snuke stands on Square A, and Fnuke stands on Square B.
You can repeat the following operation any number of times:
Choose Snuke or Fnuke, and make him jump one or two squares to the right. The destination must be one of the squares, and it must not contain a rock or the other person.
You want to repeat this operation so that Snuke will stand on Square C and Fnuke will stand on Square D.
Determine whether this is possible.
Constraints
4≤N≤200000
S is a string of length N consisting of . and #.
1≤A,B,C,D≤N
Square A, B, C and D do not contain a rock.
A, B, C and D are all different.
A<B
A<C
B<D
输入：
Input is given from Standard Input in the following format:
N A B C D
S
输出:
Print Yes if the objective is achievable, and No if it is not.
题目大意：
有N个正方形排成一行，编号为1、2、…，N从左到右。给定一个长度为N的字符串S:只包括‘.’和‘#’。如果S的第i个字符是‘#’，则方块i包含一块石头;如果S的第i个字符是。，则正方形i是空的。一开始，Snuke站在Square A上，Fnuke站在Square B上。您可以重复以下操作任意次数:选择Snuke或Fnuke，让他向右跳一两个方块。目标必须是其中一个方块，并且它不能包含一块石头或另一个人。您希望重复此操作，以便Snuke将站在正方形C上，而Fnuke将站在正方形D上。确定这是否可能。
思路：
第一步判断a,c间及b,d间是否有两个连续的石头，若有，直接输出NO；
第二步判断c和d谁在前面，因为a<b，则如果d<c，则说明a一定要跳过b，判断能否跳过即可（通过第一步的c<d一定可以到达）。

#include<bits/stdc++.h>
using namespace std;
string str;
int main()
{int n,a,b,c,d;cin>>n>>a>>b>>c>>d;cin>>str;int v=0;for(int i=a; i<c-1; i++)//第一步判断{if(str[i]==str[i+1]&&str[i]=='#'){v=1;break;}}for(int i=b; i<d-1; i++)//第一步判断{if(str[i]==str[i+1]&&str[i]=='#'){v=1;break;}}if(v==1) printf("No\n");else{if(c>d)//第二步判断{int u=0;for(int i=b-1;i<=d-1;i++){if(str[i]==str[i-1]&&str[i]==str[i+1]&&str[i]=='.'){u=1;break;}}if(u==0){printf("No\n");}else printf("Yes\n");}else printf("Yes\n");}return 0;
}