题目描述
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 #include2 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\n");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\n");28 }else{29 printf("No\n");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\n");59 }else{60 printf("No\n");61 }62 }63 return 0 ;64 }