cf1468k.md

提示 1： 你放的障碍物得有作用——至少得挡住一次行动。

提示 2： 满足条件的位置并不多，枚举即可。

如果你放的障碍物跟路径没有任何关系，那么最终到达的位置也不会变，所以不合题意。

因此，你只能放在路径上的某个位置，挡住其中一次操作，才可能改变最终到达的点。

而路径上的点总共只有 $\mathcal{O}(n)$ 个，因此枚举路径上的点，模拟 $n$ 步后到达的点看是否为 $(0,0)$ 即可。

关键——实际的答案集比较明确，同时 $n=5000$ 允许模拟。

时间复杂度为 $\mathcal{O}(n^2)$ 。

具体代码如下——

Python 做法如下——

def main():
    d = {
        'L': (-1, 0), 
        'R': (1, 0),
        'D': (0, -1),
        'U': (0, 1)
    }

    t = II()
    outs = []

    for _ in range(t):
        s = I()
        x, y = 0, 0
        
        cx, cy = 0, 0
        for c in s:
            dx, dy = d[c]
            cx += dx
            cy += dy
            
            if cx != 0 or cy != 0:
                vx, vy = 0, 0
                
                for c in s:
                    tx, ty = d[c]
                    
                    if vx + tx != cx or vy + ty != cy:
                        vx += tx
                        vy += ty
                
                if vx == 0 and vy == 0:
                    x, y = cx, cy
        
        outs.append(f'{x} {y}')

    print('\n'.join(outs))

C++ 做法如下——

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    map<char, pair<int, int>> mp;
    mp['L'] = {-1, 0};
    mp['R'] = {1, 0};
    mp['D'] = {0, -1};
    mp['U'] = {0, 1};

    int t;
    cin >> t;

    while (t --) {
        string s;
        cin >> s;

        int x = 0, y = 0, cx = 0, cy = 0;
        for (auto &c: s) {
            auto &[dx, dy] = mp[c];
            cx += dx;
            cy += dy;

            if (cx || cy) {
                int vx = 0, vy = 0;
                
                for (auto &nc: s) {
                    auto &[tx, ty] = mp[nc];
                    if (vx + tx != cx || vy + ty != cy) {
                        vx += tx;
                        vy += ty;
                    }
                }

                if (!vx && !vy)
                    x = cx, y = cy;
            }
        }

        cout << x << ' ' << y << '\n';
    }

    return 0;
}