# CFr 811 D. Vladik and Favorite Game ( Interactive, Ad hoc )

Problem - 811D - Codeforces

1 ≤ N, M ≤ 100

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

const int MAXN = 100;
const int MAXM = 100;

int N, M;
string G[ MAXN ];

int gx, gy;

void run( char dir, int &x, int &y ) {
static int button = 0;
while( ++button > 2 * N * M );
cout << dir << endl;
cin >> x >> y;
if( x == -1 ) assert( 0 );
--x, --y;
if( x == gx and y == gy ) exit( 0 );
}

char rev( char dir, bool opp ) {
if( opp ) {
if( dir == 'L' ) dir = 'R';
else if( dir == 'R' ) dir = 'L';
else if( dir == 'U' ) dir = 'D';
else if( dir == 'D' ) dir = 'U';
}
return dir;
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ) {
cin >> G[ i ];
for( int j = 0; j < M; ++j ) {
if( G[ i ][ j ] == 'F' ) {
gx = i, gy = j;
break;
}
}
}
// !!! 1 ≤ N, M ≤ 100
int x = 0, y = 0;
if( N == 1 ) {
run( 'R', x, y );
if( x + y == 0 ) {
while( G[ x ][ y ] != 'F' ) {
run( 'L', x, y );
}
} else {
while( G[ x ][ y ] != 'F' ) {
run( 'R', x, y );
}
}
} else if( M == 1 ) {
run( 'D', x, y );
if( x + y == 0 ) {
while( G[ x ][ y ] != 'F' ) {
run( 'U', x, y );
}
} else {
while( G[ x ][ y ] != 'F' ) {
run( 'D', x, y );
}
}
}
bool opp_lr = false, opp_ud = false;
if( G[ x ][ y + 1 ] == '*' ) {
run( 'D', x, y );
if( x + y == 0 ) {
opp_ud = true;
} else {
run( 'U', x, y );
}
while( G[ x ][ y + 1 ] == '*' ) {
run( rev( 'D', opp_ud ), x, y );
}
int qq = x + y;
run( 'R', x, y );
if( x + y == qq ) {
opp_lr = true;
}
} else {
run( 'R', x, y );
if( x + y == 0 ) {
opp_lr = true;
} else {
run( 'L', x, y );
}
while( G[ x + 1 ][ y ] == '*' ) {
run( rev( 'R', opp_lr ), x, y );
}
int qq = x + y;
run( 'D', x, y );
if( x + y == qq ) {
opp_ud = true;
}
}
static int vis[ MAXN ][ MAXM ];
static int pre[ MAXN ][ MAXM ];
static const int dx[] = { 0, 1, 0, -1 };
static const int dy[] = { 1, 0, -1, 0 };
string mov;
string haha = "RDLU";
{
int sx = x, sy = y;
queue< pair< int, int > > que;
que.emplace( sx, sy );
vis[ sx ][ sy ] = 1;
while( not que.empty() ) {
int p, q;
tie( p, q ) = que.front();
que.pop();
if( p == gx and q == gy ) break;
for( int di = 0; di < 4; ++di ) {
int np = p + dx[ di ];
int nq = q + dy[ di ];
if( not ( 0 <= np and np < N and 0 <= nq and nq < M ) ) continue;
if( G[ np ][ nq ] == '*' ) continue;
if( vis[ np ][ nq ] ) continue;
vis[ np ][ nq ] = 1;
pre[ np ][ nq ] = di;
que.emplace( np, nq );
}
}
for( int p = gx, q = gy; not ( p == sx and q == sy ); ) {
int dd = pre[ p ][ q ];
mov += haha[ dd ];
p -= dx[ dd ];
q -= dy[ dd ];
}
}
reverse( mov.begin(), mov.end() );
for( int i = 0; i < mov.size(); ++i ) {
if( mov[ i ] == 'L' or mov[ i ] == 'R' ) {
run( rev( mov[ i ], opp_lr ), x, y );
} else {
run( rev( mov[ i ], opp_ud ), x, y );
}
}
assert( 0 );
return 0;
}
```