您的位置: 首页  >  IT文章  >  【思维】Kenken Race

【思维】Kenken Race

分类: IT文章 • 2023-11-11 15:47:00

题目描述

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.

样例输入

7 1 3 6 7
.#..#..

样例输出

Yes

提示

The objective is achievable by, for example, moving the two persons as follows. (A and B represent Snuke and Fnuke, respectively.)

A#B.#..
A#.B#..
.#AB#..
.#A.#B.
.#.A#B.
.#.A#.B
.#..#AB

 
 
【题解】：
　　题目没有给定A,C与B,D之间的关系，所以我们分类讨论，
　　如果C==D，则无解，
　　如果两个区间不重叠，那么我们只要单独判断每一个区间内是否合法。
　　如果两个区间是相交的，那么我们需要判断一下中间是否有三个空位让A跳过去。先判断B是否能到D，如果不能，则无解，如果可以，还需要在路途中A，C路上是否有三个阻碍物，不然无法跳出去。
 
 1 #include<bits/stdc++.h>
 2 using namespace std ;
 3 const int N = 2e5+100;
 4 char s[N];
 5 int main (){
 6     int n,A,B,C,D;
 7     scanf("%d%d%d%d%d",&n,&A,&B,&C,&D);
 8     scanf("%s",s+1);
 9     if( C == D ){
10         printf("No
");
11     }else if( C < D ){
12         int flag = 1 ;
13         // if( s[C] == '#' || s[D] == '#' ) flag = 0 ;
14         for ( int i = A ; i < C ; i++ ){
15             if ( s[i] == '#' && s[i+1] == '#' ){
16                 flag = 0;
17                 break ;
18             }
19         }
20         for ( int i = B ; i < D ; i++ ){
21             if ( s[i] == '#' && s[i+1] == '#' ){
22                 flag = 0;
23                 break ;
24             }
25         }
26         if( flag ){
27             printf("Yes
");
28         }else{
29             printf("No
");
30         }
31     }else{
32         int flag = 1 ;
33         for ( int i = B ; i < D ; i++ ){
34             if ( s[i] == '#' && s[i+1] == '#' ){
35                 flag = 0;
36                 break ;
37             }
38         }
39         for ( int i = A ; i < C ; i++ ){
40             if ( 
41             (s[i] == '#' && s[i+1] == '#') ||
42             (s[i] == '#' && i+1 == D ) ||
43             (s[i+1] == '#' && i == D ) 
44             ){
45                 flag = 0;
46                 break ;
47             }
48         }
49          
50         int f = 0 ;
51         for ( int i = B  ; i <= D-1 ; i++ ){
52             if ( s[i-1] == '.' && s[i] == '.' && s[i+1] == '.' ){
53                 f = 1 ;
54                 break;
55             }
56         }
57         if( flag || f ){
58             printf("Yes
");
59         }else{
60             printf("No
");
61         }
62     }
63     return 0 ;
64 }
Kenken Race

相关推荐