QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394503 | #7751. Palindrome Path | juruoA | WA | 1ms | 3932kb | C++14 | 5.7kb | 2024-04-20 15:23:29 | 2024-04-20 15:23:29 |
Judging History
answer
#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf;
inline li read(){
li ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
f = (ch == '-') ? -1 : 1;
ch = getchar();
}
while(ch <= '9' && ch >= '0'){
ans = ans * 10 + (ch ^ 48);
ch = getchar();
}
return ans * f;
}
li a[101][101];
pair<li, li> s, t;
li vis[101][101], n, m, sum;
li dir[101][101];
queue<pair<li, li>> q;
char move[] = {'U', 'R', 'L', 'D'};
li dx[] = {-1, 0, 0, 1};
li dy[] = {0, 1, -1, 0};
li rev[] = {3, 2, 1, 0};
li get(char s){
if(s == 'U') return 0;
else if(s == 'R') return 1;
else if(s == 'L') return 2;
else return 3;
}
void check_ifsolved(){
li ans = 0;
q.push(t);
vis[t.first][t.second] = 1;
while(!q.empty()){
ans++;
li x = q.front().first, y = q.front().second; q.pop();
for(li i = 0; i < 4; i++){
li tx = x + dx[i], ty = y + dy[i];
if(1 <= tx && tx <= n && 1 <= ty && ty <= m && !vis[tx][ty] && a[tx][ty]){
q.push({tx, ty});
dir[tx][ty] = i;
vis[tx][ty] = 1;
}
}
}
memset(vis, 0, sizeof vis);
// cout << ans << " " << sum << endl;
if(ans != sum){
printf("-1\n");
exit(0);
}
}
bool go(li x, li y){
if(1 <= x && x <= n && 1 <= y && y <= m){
if(a[x][y]) return 1;
}
return 0;
}
string ans, temp, ans2;
bool can[35][35][35][35];
li way[35][35][35][35];
queue<pair<pair<li, li>, pair<li, li>>> qu;
// void bfs(){
// qu.push({s, t});
// can[s.first][s.second][t.first][t.second] = 1;
// while(!qu.empty()){
// auto x = qu.front().first, y = qu.front().second;
// if(x == y){
// string sum = "";
// while(x != s || y != t){
// sum += way[x.first][x.second][y.first][y.second];
// }
// break;
// }
// for(li i = 0; i < 4; i++){
// pair<li, li> tx = {x.first + dx[i], x.second + dy[i]}, ty = {y.first + dx[rev[i]], y.second + dy[rev[i]]};
// if(!go(tx.first, tx.second)) tx = x;
// if(!go(ty.first, ty.second)) continue;
// if(can[tx.first][tx.second][ty.first][ty.second]) continue;
// can[tx.first][tx.second][ty.first][ty.second] = 1;
// way[tx.first][tx.second][ty.first][ty.second] = i;
// qu.push({tx, ty});
// }
// }
// }
li dfs(pair<li, li> x, pair<li, li> y){
// cout << x.first << " " << x.second << " " << y.first << " " << y.second << endl;
if(x == y) return 1;
// if(can[x.first][x.second][y.first][y.second]) return 0;
for(li i = 0; i < 4; i++){
// cout << "dfs " << x.first << " " << x.second << " " << y.first << " " << y.second << endl;
pair<li, li> tx = {x.first + dx[i], x.second + dy[i]}, ty = {y.first + dx[rev[i]], y.second + dy[rev[i]]};
if(!go(tx.first, tx.second)) tx = x;
// printf("id = %lld:\n", i);
// printf("to %lld %lld %lld %lld\n", tx.first, tx.second, ty.first, ty.second);
if(go(ty.first, ty.second)){
// printf("to %lld %lld %lld %lld\n", tx.first, tx.second, ty.first, ty.second);
if(can[tx.first][tx.second][ty.first][ty.second]) continue;
can[tx.first][tx.second][ty.first][ty.second] = 1;
ans2 += move[i];
if(dfs(tx, ty)) return 1;
ans2.pop_back();
// if(!go(y.first + dx[i], y.second + dy[i])) ty = y;
// else continue;
}
if(!go(y.first + dx[i], y.second + dy[i])){
ty = y;
// printf("to %lld %lld %lld %lld\n", tx.first, tx.second, ty.first, ty.second);
if(can[tx.first][tx.second][ty.first][ty.second]) continue;
can[tx.first][tx.second][ty.first][ty.second] = 1;
ans2 += move[i];
if(dfs(tx, ty)) return 1;
ans2.pop_back();
}
// can[tx.first][tx.second][ty.first][ty.second] = 0;
}
return 0;
}
int main(){
// freopen("wonderful.ans", "r", stdin);
// freopen("www.ww", "w", stdout);
n = read(), m = read();
for(li i = 1; i <= n; i++){
for(li j = 1; j <= m; j++){
a[i][j] = getchar();
while(a[i][j] > '1' || a[i][j] < '0') a[i][j] = getchar();
a[i][j] -= '0';
sum += a[i][j];
}
}
s.first = read(), s.second = read(), t.first = read(), t.second = read();
check_ifsolved();
for(li i = 1; i <= n; i++){
for(li j = 1; j <= m; j++){
// puts("-----------");
string s = "";
if(t == make_pair(i, j)) continue;
li x = i, y = j;
// cout << i << " " << j << endl;
while(t != make_pair(x, y)){
s += move[rev[dir[x][y]]];
x -= dx[dir[x][y]], y -= dy[dir[x][y]];
// cout << x << " " << y << endl;
}
// cout << i << " " << j << endl;
reverse(s.begin(), s.end());
temp += s;
// cout << s;
for(li k = 0; k < s.length(); k++) s[k] = move[rev[get(s[k])]];
reverse(s.begin(), s.end());
temp += s;
// cout << s << endl;
}
}
// cout << "?" << endl;
// reverse(temp.begin(), temp.end());
ans += temp;
for(char x : temp){
li d = get(x);
pair<li, li> tt = s;
s.first += dx[d], s.second += dy[d];
if(!go(s.first, s.second)){
s = tt;
}
// cout << s.first << " " << s.second << endl;
}
// cout << "?" << endl;
can[s.first][s.second][t.first][t.second] = 1;
dfs(s, t);
// cout << ans2 << endl;
ans += ans2;
reverse(ans2.begin(), ans2.end());
ans += ans2;
reverse(temp.begin(), temp.end());
ans += temp;
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3648kb
input:
2 2 11 11 1 1 2 2
output:
DRLUDURLRDLUULDRLRUDULRD
result:
ok Valid Solution (Length = 24).
Test #2:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DDDRLUUUDDDUUUDDDLRUUUDDDLLRRUUUDDRLUUDDUUDDLRUUDDLLRRUUDRLUDUDLRUDLLRRURLLRLLRRUDUDUDLUDRURDDLLUULDDDRRRDLUUUULLDRDDRDLLUUUULDRRRDDDLUULLDDRURDULDUDUDURRLLRLLRURRLLDURLDUDULRDUURRLLDDUURLDDUUDDUULRDDUUURRLLDDDUUURLDDDUUUDDDUUULRDDD
result:
ok Valid Solution (Length = 232).
Test #5:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDDDRRRRLLLLUUUUDDDDRRRLLLUUUUDDDDRRLLUUUUDDDDRLUUUUDDDDUUUUDDRRRDULLLUUDDRRDULLUUDDRDULUUDDDUUUDDDUUUDDRRRRLLLLUUDDRRRLLLUUDDRRLLUUDDRLUUDDUURRRDULLLRRDULLRDULDUDURRRRLLLLRRRLLLRRLLRLRRRRDDLLLLDDRRRRLRLLRRLLLRRRLLLLRRRRUDUDLUDRLLUDRRLLLUDRRRUUDDUULRDDUULLRRDDUULLLRRRDDUULLLLRRRRDDUUUDDDUUUDDDUULUDR...
result:
ok Valid Solution (Length = 384).
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3720kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
DDUUDDLRUUDDLLRRUUDUDUDURLLRUURDULDDUUDUDDUDUURRLLDDUURLDDUUDDUURDRULLUUDDRRDDUULLURDRUUDDUUDDLRUUDDLLRRUUDUDDUDUUDDLUDRUURLLRUDUDUDUURRLLDDUURLDDUUDD
result:
wrong answer End Point Is (3,1), Not (er = 3, ec = 2)