#include #define rep(i,n) for(int i = 0; i < (int)(n); i++) using namespace std; using LL = long long; using P = pair; using vv = vector>; const int INF = (int)1e9; const LL LINF = (LL)1e18; const double eps = 1e-5; const double init_p = 0.20; //const int min_p = 6; //const int max_p = 15; int H, W, poss; double p, back; double h[20][21], v[21][20]; string bfs(){ int dist[20][20]; rep(i,20){ rep(j,20) dist[i][j] = -1; } dist[0][0] = 0; queue

q; q.emplace(0, 0); while(!q.empty()){ pair p = q.front(); q.pop(); int y = p.first, x = p.second; int d = dist[y][x]; if(v[y][x] < back && dist[y-1][x] == -1){ dist[y-1][x] = d + 1; q.emplace(y - 1, x); } if(v[y+1][x] < back && dist[y+1][x] == -1){ dist[y+1][x] = d + 1; q.emplace(y + 1, x); } if(h[y][x] < back && dist[y][x-1] == -1){ dist[y][x-1] = d + 1; q.emplace(y, x - 1); } if(h[y][x+1] < back && dist[y][x+1] == -1){ dist[y][x+1] = d + 1; q.emplace(y, x + 1); } } string res; int y = 19, x = 19; if(dist[y][x] == -1){ rep(i,19) res.push_back('R'); rep(i,19) res.push_back('D'); return res; } while(y != 0 || x != 0){ int d = dist[y][x]; if(v[y][x] < back && dist[y-1][x] == d - 1){ res.push_back('D'); y--; } else if(v[y+1][x] < back && dist[y+1][x] == d - 1){ res.push_back('U'); y++; } else if(h[y][x] < back && dist[y][x-1] == d - 1){ res.push_back('R'); x--; } else if(h[y][x+1] < back && dist[y][x+1] == d - 1){ res.push_back('L'); x++; } else break; } reverse(res.begin(), res.end()); return res; } int main(){ cin >> H >> W >> poss; assert(H == 20 && W == 20); //assert(min_p <= poss && poss <= max_p); p = poss; p /= 100; back = p * 5.0; rep(i,20){ h[i][0] = 1.0; h[i][20] = 1.0; } rep(j,20){ v[0][j] = 1.0; v[20][j] = 1.0; } rep(i,20){ rep(j,19) h[i][j+1] = init_p; } rep(i,19){ rep(j,20) v[i+1][j] = init_p; } rep(trial,1001){ string ans = bfs(); cout << ans << endl; int res; cin >> res; if(res == -1){ cerr << "score = " << 1000 - trial << endl; break; } int y = 0, x = 0; int siz = ans.size(); rep(i,res){ char c = ans[i]; if(c == 'U') v[y][x] = 0, y--; if(c == 'D') v[y+1][x] = 0, y++; if(c == 'L') h[y][x] = 0, x--; if(c == 'R') h[y][x+1] = 0, x++; } if(res < siz){ char c = ans[res]; if(c == 'U' && v[y][x] > eps) v[y][x] = 1.0 - (1.0 - v[y][x]) * p; if(c == 'D' && v[y+1][x] > eps) v[y+1][x] = 1.0 - (1.0 - v[y+1][x]) * p; if(c == 'L' && h[y][x] > eps) h[y][x] = 1.0 - (1.0 - h[y][x]) * p; if(c == 'R' && h[y][x+1] > eps) h[y][x+1] = 1.0 - (1.0 - h[y][x+1]) * p; } } return 0; }