「AtCoder AGC034-A」Kenken Race

Description

给定一个长度为 $n$ 的线性地图 $\{s\}$，# 表示障碍，. 表示可以停留。小 $\rm X$ 和小 $\rm Y$ 分别站在 $a$ 处和 $b$ 处，现在小 $\rm X$ 想去 $c$，小 $\rm Y$ 想去 $d$ 。一个人一次只能走一格或两格，不能站在障碍和另一个人所在的位置，也不能反向走。求能否使小 $\rm X$ 和小 $\rm Y$ 都到达目的地。

$(4 \leq n \leq 2 \times 10^5,1 \leq a,b,c,d \leq n;a,b,c,d$ 互不相同，且 $a < b < d,a < c;s_a,s_b,s_c,s_d$ 均不为 # $)$

Source

[AtCoder]AGC034-A

Solution

首先保证 $d$ 在 $c$ 的右端，即 $d > c$（如果 $d < c$ 则交换小 $\rm X$ 和小 $\rm Y$）。

接下来就可以分三种情况考虑了。

第一种情况：

显然两个人互不影响，各走各的。如果 $ac$ 之间存在至少两个连续的 #，则小 $\rm X$ 不能到达目的地，$bd$ 同理。

第二种情况：

我们可以先让小 $\rm Y$ 先到达目的地，这样两人仍然互不影响。所以也只需要判断是否存在至少两个连续的 # 。

第三种情况：

还是先判断是否存在至少两个连续的 #（保证小 $\rm X$ 能到达 $c$，小 $\rm Y$ 能到达 $d$）。但是注意小 $\rm X$ 不论怎样都会影响到小 $\rm Y$，所以可以把小 $\rm X$ 看成一个可以放置在任何空位的障碍。当 $ac$ 之间存在至少三个连续的 . 时，就可以先让小 $\rm X$ 到达它们中间的那个点（即把 ... 变成 .#.）。这样就能使小 $\rm Y$ 到达 $d$，然后小 $\rm X$ 就不受影响了（直接到 $c$）。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

inline void readChar(char &c) {
    for (c = getchar(); c != '.' && c != '#'; c = getchar());
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 2e5;
int n, a, b, c, d;
char s[MAXN + 5];

int main() {
    read(n), read(a), read(b), read(c), read(d);
    if (d < c) swap(a, b), swap(c, d);//确保 d > c 
    for (int i = 1; i <= n; ++i) readChar(s[i]);
    for (int i = a; i <= c; ++i)
        if (s[i] == '#' && s[i - 1] == '#') {
            puts("No");//判断 ac 间是否存在两个连续的 # 
            return 0;
        }
    for (int i = b; i <= d; ++i)
        if (s[i] == '#' && s[i - 1] == '#') {
            puts("No");//判断 bd 间是否存在两个连续的 # 
            return 0;
        }
    if (a < b) {//b 先到 d，a 再到 b（第一、二种情况） 
        puts("Yes");
        return 0;
    }
    for (int i = a; i <= c; ++i)//让 a 到一个合适的位置，使 b 能够到达 d
        if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
            puts("Yes");
            return 0;
        }
    puts("No");
    return 0;
}