/*
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstdlib>
using namespace std;
vector<char> graph[255];
int N,M;
int toll[256][256];
///A -> ?
int near[256]; ///bfs or dfs 의 visted
char start;
char goal;
int nearest(char location,int pay)
{
int a;
int best=-1;
char best_shot;
int i;
if(location==goal)
{
return pay;
}
if(near[location]==-1||near[location]>pay)
{
near[location] = pay;
}
else
{
return -1;
}
//printf("%c ",location);
for(i = 0; i < graph[location].size(); i++)
{
a = nearest(graph[location][i],pay+toll[location][graph[location][i]]);
if(best == -1||best > a&&a!=-1)
{//printf("\n%c ",location);
best = a;
best_shot = graph[location][i];
}
}
if(best != -1)
{
//best += toll[location][best_shot];
//printf("|");
}
return best;
}
int main()
{
int i;
int input3;
char input1,input2;
for(i = 0; i < 256; i++)
{
near[i] = -1;
}
scanf("%d %d ",&N,&M);
for(i = 0; i < M; i++)
{
scanf("%c %c %d ",&input1,&input2,&input3);
graph[(int)input1].push_back(input2);
graph[(int)input2].push_back(input1);
toll[(int)input1][(int)input2]=input3;
toll[(int)input2][(int)input1]=input3;
}
scanf("%c %c",&start,&goal);
//puts("");
printf("%d",nearest(start,0));
return 0;
}*/
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstdlib>
using namespace std;
const int px[4] = {-1,1,0,0};
const int py[4] = {0,0,-1,1};
const char pc[5] = "DULR";
int canmove;
queue<int> que[2]; //xy
queue<char*> answer;
char map[100][100];
bool visted[100][100];
vector<int> fire[2];
int n,m;
int ex,ey;
int abs(int n){return n<0?-n:n;}
char* bfs()
{
char str[1000];
int i=0,j,k,days=0;
int ways=1;
int after_ways=1;
while(ways!= 0)
{
ways = after_ways;
after_ways = 0;
days++;
for(i = 0;i < ways;i++)
{
for(j = 0;j < 4;j++)
{
sprintf(str,"%s%c",answer.back,pc[j]);
if(que[0].back()+py[j]<0||que[1].back()+px[j]<0)
{
continue;
}
if(que[0].back()+py[j]==ey||que[1].back()+px[j]==ex)
{
printf(str);
}
if(que[0].back()+py[j]>=n||que[1].back()+px[j]>=m)
{
out:
continue;
}
for(k = 0;k < fire[1].size();k++)
{
if(abs((int)que[0].back()+py[j]-fire[0])+abs((int)que[1].back()+px[j]-fire[1])<=days/canmove)
{
goto out;
}
}
que[0].push(que[0].back()+py[j]);
que[1].push(que[1].back()+px[j]);
answer.push(str);
after_ways++;
}
que[1].pop();
que[2].pop();
answer.pop();
}
}
}
int main()
{
int i,j;
scanf("%d%d%d ",&n,&m,&canmove);
for(i = 0;i < n;i++)
{
for(j = 0;j < m;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='F')
{
fire[0].push_back(i);
fire[1].push_back(j);
}
if(map[i][j]=='Y')
{
que[0].push(i);
que[1].push(j);
}
if(map[i][j]=='E')
{
ey=i;
ex=j;
}
}
scanf(" ");
}
answer.push("");
bfs();
}
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⣀⣀⣀⣀⣀⣀⣀⣠⡖⠒⠒⠒⠒⠒⢲⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡶⠶⠖⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠶⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢀⣰⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⡆⠀⠀⠀⠀⠀⠀
⠀⠀⢀⠟⠁⠀⠀⢠⡌⠉⢡⠀⢸⠀⠀⡄⠉⠉⡄⢸⡇⠀⠈⢹⣏⠉⠁⡇⠀⠀⢠⠉⠉⠉⢡⠀⠀⠀⠹⣤⡀⠀⠀⠀⠀
⠀⠀⡟⠀⠀⠀⠀⠘⢇⣀⡸⠀⢸⠃⠀⡇⠀⠀⡇⢸⡧⠀⠠⠃⠀⠛⠄⡇⠀⠀⠘⠤⠤⠤⠜⠀⠀⠀⠀⠈⡇⠀⠀⠀⠀
⠀⠀⢇⠀⠀⠀⠀⠀⢠⠀⠀⠀⠘⠀⠀⢇⣀⣀⠇⢸⡇⠀⠘⢻⡟⠛⣃⡇⠀⠀⣀⣇⣀⣀⣇⡀⠀⠀⠀⠀⡇⠀⠀⠀⠀
⠀⠀⠘⠄⡀⠀⠀⠀⠒⠒⠒⠒⠒⠀⠀⠀⠀⠀⠀⠘⠃⠀⠀ ⡇⠀⠀⠀⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡤⠶⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠑⠒⢤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⡤⠄⠒⠉⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠈⠉⠙⠒⠒⠤⠤⠤⠤⠤⠤⠤⠤⢤⡄⠀⠀⣤⠤⠤⠒⠒⠒⠒⠒⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⢸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣤⡎⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠒⠒⣶⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡶⠉⠹⣶⡀⠀⠀⠀⠀⠀⣀⣶⠃⠀⠀⣩⡇⠀⠀
⢸⠉⢹⡀⠀⠀⠀⠀⠀⠀⡰⠋⠘⢻⡆⠀⠀⣀⣀⣀⣀⣀⣀⣀⣀⣿⠀⠀⠀⣾⠇⣀⣀⣀⠾⠉⠁⠀⠀⠀⠀⣿⠀⠀⠀
⢸⣀⠀⠈⠉⠶⢆⣀⣀⣀⢧⣄⠀⠈⠳⠛⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠿⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠙⢧⡀⠀⠀⠀⠀⠀⠛⠛⠻⠇⠀⠀⣶⣶⠀⠀⠀⠀⣀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠛⠛⠀⠀⠀⠀⣉⣀⣀⣀⣉⣉⠴⢶⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠛⠛⠛⠛⠛⠛⠉⠉⠉⠉⠉⠉⢀⣸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⢰⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡀⠀⠀⠀
⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⠤⣄⣀⡀⠀⠀⢀⣀⣠⠼⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀
⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠛⠛⠛⠛⠋⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀
⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠉⠀⠀⠀
⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⠈⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠦⣄⠀⠀
⠀⠀⠀⠀⠀⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⣀⣀⣀⡀⠀⠘⠓⡄
⠀⠀⠀⠀⣸⠋⠀⠀⢀⣤⠼⠛⠛⠛⠛⠛⠛⠛⠛⠛⠻⣿⠛⠛⠛⠛⠛⠛⠛⠛⠛⠛⠛⠛⠉⠉⢙⣿⠀⠈⠛⠷⠤⠤⠇
⠀⠀⠀⠀⠯⣀⣠⠴⠞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⢤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠼⠁⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠒⠒⠒⠒⠒⠒⠒⠚⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀