#include // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; void print0(){}; template void print0(H h,T... t){cout<void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} void perr0(){}; template void perr0(H h,T... t){cerr<void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);} void ioinit() { cout<; using tii = tuple; struct point { int i; int j; }; bool operator==(const point &lhs, const point &rhs) { return (lhs.i == rhs.i && lhs.j == rhs.j); } bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); } bool operator<(const point &lhs, const point &rhs) { if (lhs.i != rhs.i) { return lhs.i < rhs.i; } return lhs.j < rhs.j; } std::ostream &operator<<(std::ostream &os, point &pt) { string s; s.push_back('('); s = s + to_string(pt.i); s = s + ", "; s = s + to_string(pt.j); s.push_back(')'); return os << s; } mt19937 engine(0); clock_t start_time; double now() { return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC; } void marathon_init() { start_time = clock(); random_device seed_gen; engine.seed(seed_gen()); } int randint(int mn, int mx) { int rng = mx - mn + 1; return mn + (engine() % rng); } double uniform(double x, double y) { const int RND = 1e8; double mean = (x + y) / 2.0; double dif = y - mean; double p = double(engine() % RND) / RND; return mean + dif * (1.0 - 2.0 * p); } bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) { const int ANNEAL_RND = 1e8; const double ANNEAL_EPS = 1e-6; double temp = cur_time * (end_temp - begin_temp) / (end_time - begin_time) + (end_time * begin_temp - end_temp * begin_time) / (end_time - begin_time); return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS); } const int N = 20; double P; const int R = 0; const int D = 1; const int L = 2; const int U = 3; vector mvs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int c2d(char c) { if (c == 'R') return R; if (c == 'D') return D; if (c == 'L') return L; if (c == 'U') return U; return -1; } char d2c(int d) { if (d == R) return 'R'; if (d == D) return 'D'; if (d == L) return 'L'; if (d == U) return 'U'; return '?'; } vector l_table[N][N]; int l_btable[N][N]; bool l_check_table() { queue que; que.push({0, 0}); vector> done(N, vector(N)); while (que.size()) { point p = que.front(); que.pop(); if (done[p.i][p.j]) continue; done[p.i][p.j] = true; for (auto mv : l_table[p.i][p.j]) { int ni = p.i + mv.i; int nj = p.j + mv.j; que.push({ni, nj}); } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!done[i][j]) return false; } } return true; } void l_maketable(int M) { if (!LOCAL) return; while (true) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { l_table[i][j].clear(); l_btable[i][j] = 0; } } set wallset; int nwall = 0; while (nwall < M) { if (randint(0, 1) == 0) { // 右 int i = randint(0, N - 1); int j = randint(0, N - 2); tii w = {0, i, j}; if (wallset.count(w)) continue; wallset.insert(w); } else { // 下 int i = randint(0, N - 2); int j = randint(0, N - 1); tii w = {1, i, j}; if (wallset.count(w)) continue; wallset.insert(w); } nwall++; } // RDLU の順 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i + 1 < N && !wallset.count({1, i, j})) { l_table[i][j].push_back({1, 0}); //下 l_btable[i][j] += (1 << D); } if (i - 1 >= 0 && !wallset.count({1, i - 1, j})) { l_table[i][j].push_back({-1, 0}); //上 l_btable[i][j] += (1 << U); } if (j + 1 < N && !wallset.count({0, i, j})) { l_table[i][j].push_back({0, 1}); //右 l_btable[i][j] += (1 << R); } if (j - 1 >= 0 && !wallset.count({0, i, j - 1})) { l_table[i][j].push_back({0, -1}); //左 l_btable[i][j] += (1 << L); } } } if (!l_check_table()) continue; perr("M=", M); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { perr0("・"); if (j + 1 < N && wallset.count({0, i, j})) { perr0("│"); } else { perr0(" "); } } perr0("\n"); for (int j = 0; j < N; j++) { if (i + 1 < N && wallset.count({1, i, j})) { perr0("─"); } else { perr0(" "); } perr0(" "); } perr0("\n"); } break; } } int request(string ops) { cout << ops << endl; if (!LOCAL) { int res; cin >> res; return res; } { bool hitwall = false; point cur = {0, 0}; point goal = {N - 1, N - 1}; for (auto op : ops) { int d = 0; if (op == 'R') { d = R; } else if (op == 'D') { d = D; } else if (op == 'L') { d = L; } else if (op == 'U') { d = U; } else { perr(ops, "!?!?"); assert(false); } if (!(l_btable[cur.i][cur.j] & (1 << d))) { hitwall = true; break; } auto mv = mvs[d]; cur = {cur.i + mv.i, cur.j + mv.j}; } if (!hitwall && cur == goal) { return -1; } } { int opnum = 0; point cur = {0, 0}; for (auto op : ops) { int d = c2d(op); if (!(l_btable[cur.i][cur.j] & (1 << d))) { return opnum; } if (uniform(0.0, 1.0) < P) { return opnum; } auto mv = mvs[d]; cur = {cur.i + mv.i, cur.j + mv.j}; opnum++; } return opnum; } } string rand_combination(string s0, int start_ind) { string s = s0; int r = 0; int d = 0; for (int j = 0; j < start_ind; j++) { if (s[j] == 'R') r++; if (s[j] == 'D') d++; } for (int i = start_ind; i < int(s.size()); i++) { if (r < N - 1 && d < N - 1) { if (randint(0, 1)) { s[i] = 'R'; r++; } else { s[i] = 'D'; d++; } } else if (r < N - 1) { s[i] = 'R'; r++; } else { s[i] = 'D'; d++; } } return s; } int revd(int d) { return (d + 2) % 4; } int edgecosts[N][N][4]; const int inf = 1000000000; const int STOPPED = 10000; const int LU = 1000; const int RND = 10; string makeop(int opid) { vector> costs(N, vector(N, inf)); vector> froms(N, vector(N, -1)); using dij = tuple; priority_queue, greater> pq; pq.push({0, {0, 0}, -1}); while (pq.size()) { point p; int frm; int cost; tie(cost, p, frm) = pq.top(); pq.pop(); if (costs[p.i][p.j] < cost) continue; costs[p.i][p.j] = cost; froms[p.i][p.j] = frm; for (int d = 0; d < 4; d++) { int ni = p.i + mvs[d].i; int nj = p.j + mvs[d].j; if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue; int nc = cost + edgecosts[p.i][p.j][d]; pq.push({nc, {ni, nj}, d}); } } point cur = {N - 1, N - 1}; point start = {0, 0}; string result; while (cur != start) { int d = froms[cur.i][cur.j]; result.push_back(d2c(d)); auto mv = mvs[revd(d)]; cur = {cur.i + mv.i, cur.j + mv.j}; } reverse(result.begin(), result.end()); return result; } void solve() { int opslimit = 1001; if (LOCAL) opslimit = 1000; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int d = 0; d < 4; d++) { edgecosts[i][j][d] = randint(1, RND); if (d == L || d == U) edgecosts[i][j][d] += LU; } } } vector> history(N, vector(N, "")); for (int opid = 1; opid <= opslimit; opid++) { string s = makeop(opid); int res = request(s); if (res < 0) { perr(opid, "success!"); perr0("score=", 1001 - opid, "\n"); return; } { point cur = {0, 0}; for (int i = 0; i < res; i++) { char c = s[i]; int d = c2d(c); edgecosts[cur.i][cur.j][d] = 0; cur = {cur.i + mvs[d].i, cur.j + mvs[d].j}; } { int i = res; char c = s[i]; int d = c2d(c); if (edgecosts[cur.i][cur.j][d] != 0) edgecosts[cur.i][cur.j][d] += STOPPED; } } if (LOCAL) { perr(res); } } perr(opslimit, "failure!"); perr0("score=0\n"); } int main() { marathon_init(); ioinit(); int _h, _w; cin >> _h >> _w >> P; P *= 0.01; int M = 200; if (LOCAL) { cin >> M; } perr("P=", P); l_maketable(M); solve(); return 0; }