寻找路径

第一行是一个正整数 T(T<=25)，表示测试数据的组数。
对于每组测试数据，
第一行是两个正整数 n 和 m ，保证 n, m 均不大于 50000。
第二行一个长度为n+m的字符串，表示第一个机器人所走的指令，保证字符串中恰好出现 n 个 "U" 以及 m 个"R"。
保证所有测试数据输入字符串的总长度不超过150000。

对于每组测试数据，输出一行只包含大写字母"U" 和"R"的字符串，表示可行的指令串。
要求在满足成功走到迷宫出口的前提下，还要保证和所给机器人的路径没有相同的边。
输出任意一个合法解即可，如果不存在合法路径，则输出一行"impossible"（不含引号）。

C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 760K, 提交时间: 2023-03-23 18:14:04

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

int main() {
	size_t T;
	cin >> T;
	while (T--) {
		size_t n, m;
		string str, res;
		cin >> n >> m >> str;
		if (str.front() == 'U' && str.back() == 'U') {
			for (size_t i = 2; i != n + m; ++i) if (str[i] == 'R' && str[i - 1] == 'R') {
				res = string(count(str.begin(), str.begin() + i, 'R'), 'R') + string(n, 'U');
				res.append(n + m - res.size(), 'R');
				break;
			}
			if (res.empty()) res = "impossible";
		}
		if (str.front() == 'U' && str.back() == 'R') {
			res = string(m, 'R') + string(n, 'U');
		}
		if (str.front() == 'R' && str.back() == 'U') {
			res = string(n, 'U') + string(m, 'R');
		}
		if (str.front() == 'R' && str.back() == 'R') {
			for (size_t i = 2; i != n + m; ++i) if (str[i] == 'U' && str[i - 1] == 'U') {
				res = string(count(str.begin(), str.begin() + i, 'U'), 'U') + string(m, 'R');
				res.append(n + m - res.size(), 'U');
				break;
			}
			if (res.empty()) res = "impossible";
		}
		cout << res << endl;
	}
}

详情