QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394769#7751. Palindrome Path_Alexande_WA 0ms3784kbC++143.1kb2024-04-20 19:24:572024-04-20 19:24:58

Judging History

你现在查看的是最新测评结果

  • [2024-04-20 19:24:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3784kb
  • [2024-04-20 19:24:57]
  • 提交

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