#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll CYCLE_PER_SEC = 2700000000; double TIME_LIMIT = 1.8; unsigned long long int get_cycle() { unsigned int low, high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((unsigned long long int) low) | ((unsigned long long int) high << 32); } double get_time(unsigned long long int begin_cycle) { return (double) (get_cycle() - begin_cycle) / CYCLE_PER_SEC; } unsigned long long xor128() { static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123; unsigned long long rt = (rx ^ (rx << 11)); rx = ry; ry = rz; rz = rw; return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8))); } const int H = 20; const int W = 20; const int DY[4] = {-1, 0, 1, 0}; const int DX[4] = {0, 1, 0, -1}; const string DS[4] = {"U", "R", "D", "L"}; const int MAX_TURN = 1000; int p; int ng_counter[H * W][H * W]; int ok_counter[H * W][H * W]; bool is_inside(int y, int x) { return 0 <= y && y < H && 0 <= x && x < W; } int calc_z(int y, int x) { return y * W + x; } struct Node { int y; int x; double value; int last_dir; Node(int y = -1, int x = -1, double value = 0.0, int last_dir = -1) { this->y = y; this->x = x; this->value = value; this->last_dir = last_dir; } bool operator>(const Node &n) const { return value > n.value; } }; class HiddenMaze { public: void init() { memset(ng_counter, 0, sizeof(ng_counter)); memset(ok_counter, 0, sizeof(ok_counter)); } void run() { ll start_cycle = get_cycle(); for (int t = 0; t < MAX_TURN; ++t) { double cur_time = get_time(start_cycle); if (cur_time < TIME_LIMIT) { vector path = find_path(); string query = path2str(path); int res = send_query(query); if (res == -1) break; update_maze_data(res, path); } else { string query = "RRRR"; int res = send_query(query); } } } int send_query(string query) { cout << query << endl; int res; cin >> res; return res; } string path2str(vector &path) { string res = ""; for (int dir : path) { res += DS[dir]; } return res; } void update_maze_data(int res, vector &path) { int cy = 0; int cx = 0; for (int i = 0; i <= res; ++i) { int dir = path[i]; int ny = cy + DY[dir]; int nx = cx + DX[dir]; int z = calc_z(cy, cx); int nz = calc_z(ny, nx); if (i == res) { ng_counter[z][nz]++; } else { ok_counter[z][nz]++; } cy = ny; cx = nx; } } double calc_wall_rate(int z, int nz) { int ok_cnt = ok_counter[z][nz]; int ng_cnt = ng_counter[z][nz]; int try_count = (ok_cnt + ng_cnt); if (try_count == 0) { return 0.5; } else { return ng_cnt * 1.0 / try_count; } } vector find_path() { priority_queue , greater> pque; pque.push(Node(0, 0, 0)); bool visited[H][W]; int history[H][W]; memset(history, -1, sizeof(history)); memset(visited, false, sizeof(visited)); while (not pque.empty()) { Node node = pque.top(); int z = calc_z(node.y, node.x); pque.pop(); if (visited[node.y][node.x]) continue; visited[node.y][node.x] = true; history[node.y][node.x] = node.last_dir; if (node.y == H - 1 && node.x == W - 1) { vector path; int cy = node.y; int cx = node.x; while (cy != 0 || cx != 0) { int dir = history[cy][cx]; path.push_back(dir); cy += DY[dir ^ 2]; cx += DX[dir ^ 2]; } reverse(path.begin(), path.end()); return path; } for (int dir = 0; dir < 4; ++dir) { int ny = node.y + DY[dir]; int nx = node.x + DX[dir]; int nz = calc_z(ny, nx); if (not is_inside(ny, nx)) continue; int ok_cnt = ok_counter[z][nz]; int ng_cnt = ng_counter[z][nz]; int try_count = ok_cnt + ng_cnt; double wall_rate = calc_wall_rate(z, nz); if (try_count > 5 && wall_rate > 0.5) continue; double value = node.value + 1000 * calc_wall_rate(z, nz) + 1.0; value += 0.0001 * (xor128() % 100); Node next(ny, nx, value, dir); pque.push(next); } } return vector(); } }; int main() { int _H, _W; cin >> _H >> _W >> p; fprintf(stderr, "H: %d, W: %d, p: %d\n", H, W, p); HiddenMaze hm; hm.run(); return 0; }