2020ICPC南京站E-Evil Coordinate 题解

题目大意

从$(0,0)$出发,给你一个代表方向的字符串,给你一个点$(x,y)$,这个点不能走,问能否在不经过这个点的情况下到达终点。

解题思路

当初打比赛的时候,说实话,真没啥思路。

打完之后看题解,这思路。。

绝了。

完全想不到只要全排列UDLR就可以了。

因为全枚举上下左右已经足够避免重复了,如果所有情况都没办法避免,那就是不行的。

只能说这思路太妙了。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

int u, d, l, r;
int per[4];
int dx, dy;

int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans *= a;
a <<= 1, b >>= 1;
}
return ans;
}

int exit(int x, int y) {
return (x == dx) && (y == dy);
}

int check() {
int x, y; x = y = 0;
int flag = 0;
rep(i, 0, 3) {
if (per[i] == 1) {
rep(i, 1, u) {
y++; flag = exit(x, y);
if (flag) return 0;
};
}
else if (per[i] == 2) {
rep(i, 1, d) {
y--; flag = exit(x, y);
if (flag) return 0;
}
}
else if (per[i] == 3) {
rep(i, 1, l) {
x--; flag = exit(x, y);
if (flag) return 0;
}
}
else {
rep(i, 1, r) {
x++; flag = exit(x, y);
if (flag) return 0;
}
}
}
return 1;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("D:\\测试用\\in.txt", "r", stdin);
//freopen("D:\\测试用\\out.txt", "w+", stdout);
int t; cin >> t;
while (t--) {
u = d = l = r = 0;
cin >> dx >> dy;
string s; cin >> s;
int len = s.length();
rep(i,0,len-1) {
if (s[i] == 'U') u++;
else if (s[i] == 'D') d++;
else if (s[i] == 'L') l++;
else r++;
}
per[0] = 1, per[1] = 2;
per[2] = 3, per[3] = 4;
if (!dx && !dy) {
cout << "Impossible" << endl;
continue;
}
int flag = 0;
do {
if (check()) {
flag = 1; break;
}
} while (next_permutation(per, per + 4));
if (flag) {
rep(i, 0, 3) {
if (per[i] == 1)
rep(i, 1, u) cout << 'U';
else if (per[i] == 2)
rep(i, 1, d) cout << 'D';
else if (per[i] == 3)
rep(i, 1, l) cout << 'L';
else rep(i, 1, r) cout << 'R';
}
}
else cout << "Impossible";
cout << endl;
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信