P9626 [ICPC2020 Nanjing R] Evil Coordinate 题解

题目的意思是初始有个机器人站在 \((0, 0)\) 位置，给你一个 UDLR 序列，你需要把这个序列重新排序，使得机器人按照这个序列走的时候不会经过 \((m_x, m_y)\)，输出排序后的序列，或报告无解。

首先我们统计出来 UDLR 的数量，统计完了这个序列就没鸟用了，我们主要考虑这些方向的数量。

std::cin >> tx >> ty >> s;
u = l = r = d = 0;
for(char i : s) {
    u += i == 'U';
    l += i == 'L';
    r += i == 'R';
    d += i == 'D';
}
if(u - d == ty && r - l == tx) { // 因为无论怎么排序终点都是不变的，所以这种情况可以直接判定无解
    std::cout << "Impossible\n";
    return;
}

之后就是爆搜，没错就是搜，不过这里有一个优化的小技巧。

std::string ans;
bool ok;
void dfs(int x, int y) {
    if(x == tx && y == ty) return; // 踩上了，这条路径不行
    if(x == tx) { // 如果 x 坐标和地雷的 x 坐标的一样了
        // 并且此时不能变更 x 坐标（l 和 r 已经用完）
        // 如果机器人的 y 坐标比地雷的小，且耗尽所用移动次数后又比地雷的大，那么机器人一定会经过地雷
        // 同理，如果机器人的 y 坐标大，且耗尽所有移动次数后又小，也是一定会经过地雷的
        // 可以使用异或的特性来简化代码
        if(!l && !r && (y > ty) ^ (y+u-d > ty)) return;
    }
    if(y == ty) { // 和上面的一样
        if(!u && !d && (x > tx) ^ (x+r-l > tx)) return;
    }
    if(!u && !l && !r && !d) return ok=1, void(); // 没有踩到地雷，这条路径就是可行的
    if(l) { // 如果还能向左走
        --l;
        ans.push_back('L');
        dfs(x-1, y);
        if(ok) return; // 如果路径已经合法了直接返回，不需要继续搜索
        ans.pop_back(); // 如果路径不合法就回溯
        ++l;
    }
    // 下面三个同理
    if(r) {
        --r;
        ans.push_back('R');
        dfs(x+1, y);
        if(ok) return;
        ans.pop_back();
        ++r;
    }
    if(d) {
        --d;
        ans.push_back('D');
        dfs(x, y-1);
        if(ok) return;
        ans.pop_back();
        ++d;
    }
    if(u) {
        --u;
        ans.push_back('U');
        dfs(x, y+1);
        if(ok) return;
        ans.pop_back();
        ++u;
    }
}

温馨提示：多测记得清空！

ans.clear();
ok = 0;
dfs(0, 0);
if(ok) std::cout << ans << '\n';
else std::cout << "Impossible\n";

P9626 [ICPC2020 Nanjing R] Evil Coordinate 题解

评论