Codeforces Round ＃416 (Div. 2) D. Vladik and Favorite Game

#include <iostream> 
#include <stdio.h> 
#include <string.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <vector> 
#include <math.h> 
#include <bitset> 
#include <algorithm> 

using namespace std;

#define X first
#define Y second
#define eps 1e-2
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;

const int N = 1e5+2;
const int INF  = 1<<30;
const int mod  = 1e9+7;

int n,m;
char ch[105][105],dr2[4]={
    'D','U','R','L'};
int pre[105][105];
int dr[4][2]={
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}},vis[105][105];
pair<int,int> pre2[105][105];
int getd(int x,int y,int xx,int yy){
    
    if(x-1==xx) return 1;
    if(x+1==xx) return 0;
    if(y-1==yy) return 3;
    return 2;
}
bool check(int x,int y){
    
    if(x>0&&x<=n&&y>0&&y<=m) return 1;
    else return 0;
}
int edx,edy;
void sol1(){
    
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(ch[i][j]=='F') edx=i,edy=j;
    int sx=1,sy=1;
    queue< pair<int,int> > q;
    q.push({
    sx,sy});
    while(q.size()){
    
        auto tp=q.front();q.pop();
        vis[tp.first][tp.second]=1;
        // cout<<tp.first<<" "<<tp.second<<endl;
        for(int i=0;i<4;i++){
    
            int x=tp.first+dr[i][0],y=tp.second+dr[i][1];
            if(vis[x][y]==1||ch[x][y]=='*'||check(x,y)==0) continue;
            q.push({
    x,y});
            vis[x][y]=1;
            pre2[x][y]=tp;
        }
    }
    // return ;
    sx=edx,sy=edy;
    // cout<<sx<<" "<<sy<<endl;
    // cout<<pre2[sx][sy].first<<" "<<pre2[sx][sy].second<<endl;
    while(sx!=1||sy!=1){
    
        int px=sx,py=sy;
        sx=pre2[px][py].first;
        sy=pre2[px][py].second;
        pre[sx][sy]=getd(sx,sy,px,py);
        // cout<<sx<<" "<<sy<<endl;
        // cout<<pre[sx][sy]<<" "<<dr2[pre[sx][sy]]<<endl;
    }
}
map<int,int> mp;
void solve(){
    
    for(int i=0;i<=3;i++) mp[i]=i;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",ch[i]+1);
    sol1();
    int sx=1,sy=1;
    while(sx!=edx||sy!=edy){
    
        int mpop=mp[pre[sx][sy]];
        // cout<<mpop<<endl;
        cout<<dr2[mpop]<<endl; 
        int tsx=sx+dr[mpop][0],tsy=sy+dr[mpop][1];
        // cout<<tsx<<" "<<tsy<<endl;
        int tx,ty;cin>>tx>>ty;
        if(tsx!=tx||tsy!=ty){
    
            if(pre[sx][sy]==1||pre[sx][sy]==0) mp[0]=1,mp[1]=0;
            else mp[2]=3,mp[3]=2;
            mpop=mp[pre[sx][sy]];
            cout<<dr2[mpop]<<endl;
            cin>>tx>>ty;
        }
        sx=tx;sy=ty;
        
    }
    return;
}

int main()
{
    
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
    int t = 1;
    //scanf("%d",&t);
    while(t--){
    
    // printf("Case %d: ",cas++);
        solve();
    }
    return 0;
}