QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394769 | #7751. Palindrome Path | _Alexande_ | WA | 0ms | 3784kb | C++14 | 3.1kb | 2024-04-20 19:24:57 | 2024-04-20 19:24:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); ++ i )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); -- i )
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
char _c; bool _f; template < class type > inline void read ( type &x ) {
_f = 0, x = 0;
while ( _c = getchar (), !isdigit ( _c ) ) if ( _c == '-' ) _f = 1;
while ( isdigit ( _c ) ) x = x * 10 + _c - '0', _c = getchar (); if ( _f ) { x = -x; }
}
template < class type > inline void chkmin ( type &x, type y ) { x = ( x <= y ? x : y ); }
template < class type > inline void chkmax ( type &x, type y ) { x = ( x >= y ? x : y ); }
const int N = 35;
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
const char ch[] = "DURL";
int n, m, sx, sy, fx, fy, cnt;
string s[N], ans;
bool vis[N][N];
vector < int > g;
bool Check ( int x, int y, int i ) {
int nx = x + dx[i], ny = y + dy[i];
if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && s[nx][ny] == '1' ) {
return true;
}
return false;
}
void move ( int p ) {
int op = p ^ 1;
int tsx = sx, tsy = sy, tfx = fx, tfy = fy, k = 0;
while ( Check ( sx, sy, op ) && Check ( fx, fy, p ) ) {
ans = ans + ch[op];
k ++;
sx += dx[op], sy += dy[op];
fx += dx[p], fy += dy[p];
}
if ( Check ( fx, fy, p ) ) {
ans = ans + ch[op];
}
for ( int i = 1; i <= k + 1; i ++ ) {
ans = ans + ch[p];
}
sx = tsx, sy = tsy, fx = tfx, fy = tfy;
sx += dx[p], sy = dy[p];
}
void dfs ( int x, int y ) {
cnt ++;
for ( int i = 0; i < 4; i ++ ) {
int nx = x + dx[i], ny = y + dy[i];
if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && s[nx][ny] == '1' && !vis[nx][ny] ) {
vis[nx][ny] = true;
move ( i );
dfs ( nx, ny );
move ( i ^ 1 );
}
}
}
bool dfs2 ( int x, int y ) {
if ( x == fx && y == fy ) {
return true;
}
for ( int i = 0; i < 4; i ++ ) {
int nx = x + dx[i], ny = y + dy[i];
if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && s[nx][ny] == '1' && !vis[nx][ny] ) {
vis[nx][ny] = true;
g.push_back ( i );
if ( dfs2 ( nx, ny ) ) {
return true;
}
g.pop_back ();
}
}
return false;
}
void Solve () {
cin >> n >> m;
for ( int i = 1; i <= n; i ++ ) {
cin >> s[i];
s[i] = " " + s[i];
}
cin >> sx >> sy >> fx >> fy;
vis[sx][sy] = true;
dfs ( sx, sy );
for ( int i = 1; i <= n; i ++ ) {
for ( int j = 1; j <= m; j ++ ) {
cnt -= ( s[i][j] == '1' );
vis[i][j] = false;
}
}
if ( cnt ) {
cout << -1;
return ;
}
vis[sx][sy] = true;
dfs2 ( sx, sy );
for ( int x : g ) {
move ( x );
}
cout << ans;
reverse ( ans.begin (), ans.end () );
cout << ans;
}
signed main () {
#ifdef judge
freopen ( "Code.in", "r", stdin );
freopen ( "Code.out", "w", stdout );
freopen ( "Code.err", "w", stderr );
#endif
Solve ();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
2 2 11 11 1 1 2 2
output:
DRDUDRLLDURDRRDRUDLLRDUDRD
result:
ok Valid Solution (Length = 26).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3628kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
UDDLRDUDUDUDULRUDUDUDUDDUDUDUDURLLRLUDUDRLLUDUDDUDUDUDUUDUDLRDDDUUUDULRUDUDUDUDRLLDULRUDDLRDUUDRLDDURLUDLLRDUDUDUDURLUDUUUDDDRLDUDUUDUDUDUDDUDULLRDUDULRLLRUDUDUDUDDUDUDUDURLUDUDUDUDRLDDU
result:
wrong answer (1,1) Not Visited