#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 int min_p = 6; const int max_p = 15; int dy[4] = {-1, 1, 0, 0}; int dx[4] = {0, 0, -1, 1}; string dir = "UDLR"; double h[20][21], v[21][20]; int H, W, poss; double p; struct node{ int y, x; double d; node(int y, int x, double d) : y(y), x(x), d(d) {} bool operator> (const node &u) const{ return d > u.d; } }; string dijkstra(){ double dist[20][20]; rep(i,20){ rep(j,20) dist[i][j] = INF; } char par[20][20]; dist[0][0] = 0; priority_queue,greater<>> pq; pq.emplace(0, 0, 0); while(!pq.empty()){ node u = pq.top(); pq.pop(); if(dist[u.y][u.x] < u.d) continue; rep(k,4){ int ny = u.y + dy[k], nx = u.x + dx[k]; if(ny < 0 || ny >= 20) continue; if(nx < 0 || nx >= 20) continue; double e = 0; if(k == 0) e = 1.0 / (1.0 - v[u.y][u.x]); else if(k == 1) e = 1.0 / (1.0 - v[u.y+1][u.x]); else if(k == 2) e = 1.0 / (1.0 - h[u.y][u.x]); else e = 1.0 / (1.0 - h[u.y][u.x+1]); double nd = u.d + e; if(dist[ny][nx] <= nd) continue; pq.emplace(ny, nx, nd); dist[ny][nx] = nd; par[ny][nx] = dir[k]; } } int now_y = 19, now_x = 19; string res; while(now_y != 0 || now_x != 0){ char c = par[now_y][now_x]; res += c; if(c == 'U') now_y++; else if(c == 'D') now_y--; else if(c == 'L') now_x++; else now_x--; } reverse(res.begin(), res.end()); return res; } double update(double now_p){ if(now_p < eps) return now_p; double wall_p = now_p + (1.0 - now_p) * p; return now_p / wall_p; } double update_all(){ double tot = 0.0; rep(i,20){ rep(j,19){ tot += h[i][j+1]; } } rep(i,19){ rep(j,20){ tot += v[i+1][j]; } } tot /= 150.0; rep(i,20){ rep(j,19){ h[i][j+1] /= tot; } } rep(i,19){ rep(j,20){ v[i+1][j] /= tot; } } } int main(){ cin >> H >> W >> poss; assert(H == 20 && W == 20); assert(min_p <= poss && poss <= max_p); p = poss; p /= 100.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] = 150.0 / 760.0; } rep(i,19){ rep(j,20) v[i+1][j] = 150.0 / 760.0; } rep(trial,1001){ //string ans = bfs(); string ans = dijkstra(); 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; */ if(c == 'U') v[y][x] = update(v[y][x]); if(c == 'D') v[y+1][x] = update(v[y+1][x]); if(c == 'L') h[y][x] = update(h[y][x]); if(c == 'R') h[y][x+1] = update(h[y][x+1]); } update_all(); } return 0; }